Codeforces Round #549 div2 1143-B Nirvana 题解

一开始看到这道题的时候还是有点伤脑筋的，一直没想出来，想了十多分钟后想到办法后AC

代码使用字符串模拟数字求得结果，getvalue()函数是求得结果，calc()函数是递归函数，用于求得最大值

这个采用的递归搜索，设定结果函数为calc()，字符串长度为n，则calc返回以下其中一个最大解：

1. getvalue( {s[0], s[1], ..., s[n-1]} )
2. getvalue( {s[0]-1, 9, ..., 9} ) //连续n-1个9
3. getvalue( {9, 9, ..., 9} ) //连续n-1个9
4. s[0] * calc( {s[1], s[2], ..., s[n-1]} )

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<string>

#include<cmath>

#include<cstring>

#include<cstdlib>

using namespace std;

typedef long long ll;

ll getvalue(string s) {

	ll sum = 1;

	for (int i = 0; i < s.size(); i++) {

		sum *= s[i] - '0';

	}

	return sum;

}

ll calc(string s) {

	string q1 = s;

	q1[0]--;

	for (int i = 1; i < q1.size(); i++)q1[i] = '9';

	return max({

		getvalue(s),

		getvalue(q1),

		getvalue(q1.substr(1)),

		(s.size() > 1) ? ((ll)(s[0] - '0')*calc(s.substr(1))) : 0

	});

}

int main() {

	string s;

	cin >> s;

	cout << calc(s) << endl;

}