记录编号	296022	评测结果	AAAAAAAAAA
题目名称	[NOIP 2000PJ]乘积最大	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2016-08-14 20:07:18	内存使用	0.60 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int n,k;
const int bit=40;
char s[50];
struct big{
	int a[100];
	big(){memset(a,0,sizeof a);}
	big(int x,int y){
		memset(a,0,sizeof a);
		for (int i=y,j=1;i>=x;i--,j++) a[j]=s[i]-'0';
	}
	void mod(){
		for (int i=1;i<=bit;i++) a[i+1]+=a[i]/10,a[i]%=10;
	}
	bool operator > (const big x)const{
		int i;
		for (i=bit;i>1&&a[i]==x.a[i];i--);
		return a[i]>x.a[i];
	}
	big operator * (const big x)const{
		big ans;
		for (int i=1;i<=bit;i++)
		for (int j=1;j<=bit;j++)
			ans.a[i+j-1]+=a[i]*x.a[j];
		ans.mod();
		return ans;
	}
	void print(){
		int i;
		for (i=49;!a[i]&&i>1;i--);
		for (;i;i--) printf("%d",a[i]);
		puts("");
	}
}dp[50][20];//dp[i][j]表示用了前i个整数和j个乘号的最大值 
big max(big x,big y){
	return x>y?x:y;
}
int main()
{
	freopen("cjzd.in","r",stdin);
	freopen("cjzd.out","w",stdout); 
	scanf("%d%d%s",&n,&k,s+1);s[0]='0';
	for (int i=1;i<=n;i++) dp[i][0]=big(1,i);
	for (int j=0;j<k;j++)
	for (int i=1;i<=n;i++)
	for (int l=i+1;l<=n;l++)
		dp[l][j+1]=max(dp[l][j+1],dp[i][j]*big(i+1,l));
	dp[n][k].print();
	return 0;
}