记录编号	246417	评测结果	AAAAAAAAAA
题目名称	乘法问题	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2016-04-06 10:21:17	内存使用	1.48 MiB

#include<cstdio>
#include<cstring>
#include<cctype>
int num[50];
char readch(){
	char ch;
	while(ch=getchar(),!isdigit(ch));
	return ch;
}
struct bigint{
	int num[70],len;
	bigint(){
		memset(num,0,sizeof(num));
		len=0;
	}
	bigint(int a){
		memset(num,0,sizeof(num));
		num[0]=a;
		len=1;
		for(int i=0;i<len;++i){
			if(num[i]>=10){
				num[i+1]+=num[i]/10;
				num[i]%=10;
				if(i+1==len)len++;
			}
		}
		
	}
	bigint operator * (bigint b){
		bigint c;
		for(int i=0;i<len;++i)
			for(int j=0;j<b.len;++j){
				c.num[i+j]+=num[i]*b.num[j];			
			}
		c.len=len+b.len-1;
		for(int i=0;i<c.len;++i){
			if(c.num[i]>=10){
				c.num[i+1]+=c.num[i]/10;
				c.num[i]%=10;
				if(i+1==c.len)c.len++;
			}
		}
		while(c.num[c.len-1]==0&&c.len>1)c.len--;//没打这一句消掉多余零被坑了。。 
		
		return c;
	}
	bigint operator +(int b){
		bigint c;
		c.len=len+1;
		for(int i=0;i<len;++i){
			c.num[i+1]=num[i];
		}
		c.num[0]=b;
		return c;
	}
	void output(){
		for(int i=len-1;i>=0;--i)printf("%d",num[i]);
	}
	bool operator <(const bigint &a)const{
		if(len!=a.len)return len<a.len;
		else{
			for(int i=len-1;i>=0;--i){
				if(num[i]<a.num[i])return true;
				else if(num[i]>a.num[i])return false;
			}
			return false;
		}	
	}
};
bigint sum[50][50];
bigint f[50][50];
int main(){
	freopen("chf.in","r",stdin);
	freopen("chf.out","w",stdout);
	int n,k;scanf("%d %d",&n,&k);
	for(int i=1;i<=n;++i){
		num[i]=readch()-'0';
	}
	for(int i=1;i<=n;++i){
		sum[i][i]=bigint(num[i]);
		for(int j=i+1;j<=n;++j){
			sum[i][j]=sum[i][j-1]+num[j];
		}
	}
	for(int i=1;i<=n;++i)f[i][0]=sum[1][i];
	bigint tmp;
	for(int i=1;i<=k;++i){
		for(int j=i+1;j<=n;++j){
			for(int q=1;i+q<=j;++q){
				
			//	printf("(%d %d)%d %d %d %d\n",j,i,j-q,i-1,j-q+1,j);
			//	f[j-q][i-1].output();
			//	printf("\nj-q,i-1\n");
			//	sum[j-q+1][j].output();
			//	printf("\nj-q+1,j\n");
				tmp=f[j-q][i-1]*sum[j-q+1][j];
			//	tmp.output();
			//	printf("\ntmp\n\n");
				if(f[j][i]<tmp)f[j][i]=tmp;
			}
		}
	}
	f[n][k].output();
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
28 25
6578945678321044101234567897
2477726525030400000
*/