1314: 乘积最大

解题思路:f[i][j]表示到索引i数字字符插入j个乘号，所能得到最大的乘积。 初始化f[i][0] 为到i索引字符结束的整数（插入了0个乘号）；r遍历字符从1到i个字符每种情况， 状态转移方程：f[i][j] = max(f[i][j],f[r-1][j-1] * num(r,i))

注意事项:声明为long long 类型， 否则可能溢出。 另外，如何字符串长度n如果大于19， 则会超出long long 数据范围。

参考代码:

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N = 1e2 + 10; 
long long f[N][N];
string s;
long long num(int r, int i){
	string s1 = s.substr(r,i - r + 1);
	return stoll(s1);
}
int main()
{
	int n, k;
	cin >> n >> k >> s;
	for(int i = 0; i < n; i ++) f[i][0] = num(0,i);
	for(int i = 0; i < n; i ++)
		for(int j = 1; j <= k; j ++)
			for(int r = 1; r <= i; r ++){
				f[i][j] = max(f[i][j],f[r-1][j-1] * num(r,i));
		}
	cout << f[n-1][k];
	return 0;
}