记录编号	51151	评测结果	AAAAAAAAAA
题目名称	[NOIP 2000PJ]乘积最大	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2012-12-12 21:10:51	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int main(){
	freopen("cjzd.in","r",stdin);
	freopen("cjzd.out","w",stdout);
	unsigned long long f[50][50]={0},pro[50][50]={0};//f[i][j]=前i个数,分成j段最大值,pro[i][j]=i到j的值
	int n,k,i,j,m;
	string s;
	scanf("%d%d",&n,&k);//长度n,分成k+1个部分
	cin>>s;
	for(i=0;i<n;i++) s[i]-='0';
	k++;
	for(i=1;i<=n;i++){
		pro[i][i]=s[i-1];
		for(j=i+1;j<=n;j++){
			pro[i][j]=pro[i][j-1]*10+s[j-1];
		}
	}
	for(i=1;i<=n;i++) f[i][1]=pro[1][i];
	for(j=2;j<=k;j++){
		for(i=2;i<=n;i++){
			for(m=1;m<i;m++){
				if(f[m][j-1]*pro[m+1][i]>f[i][j]) f[i][j]=f[m][j-1]*pro[m+1][i];
			}
		}
	}
	cout<<f[n][k]<<endl;
	return 0;
}