记录编号	282370	评测结果	AAAAA
题目名称	[NOI 1996]添加号	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.302 s
提交时间	2016-07-13 15:22:44	内存使用	33.71 MiB

#include<stdio.h>
#include<string.h>
//================ struct ================//
struct Bign{
	int big[210],len;
};
Bign a[210][210]={0},f[25][210]={0};
//================ variable ================//
char A[210]={0};
int n,m;
//================ function ================//
int min(int x,int y){return x<y?x:y;} 
//================ bign_add ================//
Bign bign_add(Bign c,Bign d)
{
	int i;
	if(c.len<d.len) c.len=d.len;
	for(i=1;i<=c.len;i++)
	{
		c.big[i]+=d.big[i];
		if(c.big[i]>=10000)
		  c.big[i+1]+=c.big[i]/10000,
		  c.big[i]%=10000;
	}
	if(c.big[c.len+1]>0) c.len++;
	return c;
}
//================ bign_multiply ================//
Bign bign_multiply(Bign c)
{
	int i;
	for(i=1;i<=c.len;i++)
	  c.big[i]*=10;
	for(i=1;i<=c.len;i++)
	{
		if(c.big[i]>=10000)
		  c.big[i+1]+=c.big[i]/10000,
		  c.big[i]%=10000;
	}
	if(c.big[c.len+1]>0) c.len++;
	return c;
}
//================ bign_change ================//
Bign bign_change(Bign c,Bign d)
{
	int i;
	for(i=1;i<=d.len;i++)
	  c.big[i]=d.big[i];
	for(;i<=c.len;i++)
	  c.big[i]=0;
	c.len=d.len;
	return c;
}
//================ bign_min ================//
bool bign_min(Bign c,Bign d)
{
	int i;
	if(c.len<d.len) return true;
	else if(c.len>d.len) return false;
	else
	{
		for(i=c.len;i>0;i--)
		  if(c.big[i]>d.big[i])
		    return false;
		  else if(c.big[i]<d.big[i])
		    return true;
	}
	return true;
}
//================ bign_print ================//
void bign_print(Bign c)
{
	int i;
	for(i=c.len;i>0;i--)
	{
		if(i==c.len||c.big[i]>=1000)
		  printf("%d",c.big[i]);
		else if(c.big[i]>=100)
		  printf("0%d",c.big[i]);
		else if(c.big[i]>=10)
		  printf("00%d",c.big[i]);
		else printf("000%d",c.big[i]);
	}
}
//================ main ================//
int _521()
{
	freopen("exam4.in","r",stdin);
	freopen("exam4.out","w",stdout);
	int i,j,k;
	scanf("%s\n%d",A,&m);
	n=strlen(A);
	for(i=1;i<=n;i++)
	  a[i][i].big[1]=A[i-1]-'0',a[i][i].len=1;
	for(i=n-1;i>=1;i--)
	  for(j=i+1;j<=n;j++)
		a[i][j]=bign_add(bign_multiply(a[i][j-1]),a[j][j]);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<i;j++)
		{
			f[0][j]=bign_change(f[0][j],a[1][j]);
			for(k=min(m,i-1);k>0;k--)
			{
				Bign temp=bign_add(f[k-1][j],a[j+1][i]);
				if(f[k][i].big[1]==0||bign_min(temp,f[k][i]))
			      f[k][i]=temp;
			}
		}
	}
	bign_print(f[m][n]);
}
int _520=_521();
int main(){;}