【题解】乘积最大[NOIP2000 提高组]

本题考察的是动态规划。（ 数据比较水，不用高精就过了）

一些变量的定义：

unsigned long long num[109][109];
unsigned long long f[109][109];

• $num_{i,j}$ 表示截取从位置 $i$ 到 $j$ 的数字串。（比如对于 11232 来说，下标从 1 开始，$num_{2,4}$ 就表示数字串 123）
• $f_{i,j}$ 表示前 $i$ 位数，插入 $j$ 个乘号的最大值

状态转移方程：

f[i][j] = max(f[i][j],f[l][j-1]*num[l+1][i]);

$l$ : 当前在 $l$ 位置插入了一个乘号，接下来还应该在 $l$ 的左边插入 $j-1$ 个乘号 。那我们可以枚举 $l$ 的位置， $l$ < $i$，取 $l$ 在不同位置的最大值。

接下来是一些我做题时的问题，可能都比较水，不过还是放上来

Q1 : 为什么一定要在 $l$ 的左边放那 $j-1$ 个乘号呢，为什么不能再 $l$ 的右边也放乘号呢，这样会不会少情况？

A1 : 不会，当 $l$ 往右边移动时，总能取到那个“你觉得会漏掉的情况”。

Q2 : 为什么是 $f_{l,{j-1}}×num_{{l+1},i}$ 而不是 $f_{{l-1},{j-1}}×num_{{l+1},i}$ ？

A2 :  要包含这个 $l$，因为乘号也可以加在 $l$ 前面的那个空，如果是前面那种写法的话，乘号只能加在 $l$ 前面的前面的那个空。 

代码：

#include
#include
#include
#include
using namespace std;
unsigned long long n,k,s;//n位数字串,k个乘号,数字串 
int t[49];//数字串
unsigned long long num[109][109];
unsigned long long f[109][109];
int main(){
	cin >> n >> k;
	cin >> s;
	for(int i=n; i>=1; i--){ 
		t[i] = s%10;
		s/=10;
	}
	for(int i=1; i<=n; i++){
		for(int j=i; j<=n; j++){
			num[i][j] = num[i][j-1]*10+t[j];
		}
	}
	for(int i=1; i<=n; i++){//预处理一下 
		f[i][0] = num[1][i];
	}
	for(int i=1; i<=n; i++){//前i位数字 
		for(int j=1; j<=i-1; j++){//插入j个乘号 
			for(int l=1; l<=i-1; l++){
				f[i][j] = max(f[i][j],f[l][j-1]*num[l+1][i]);
			}
		}
	}
	cout << f[n][k];
	return 0;
}