记录编号	195483	评测结果	AAAAA
题目名称	[NOI 1996]添加号	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.921 s
提交时间	2015-10-18 21:45:31	内存使用	39.04 MiB

#define Max(a,b)((a)>(b)?(a):(b))

#include<cstdio>
#include<cstring>

using namespace std;

struct BIGNUM{
	int s[205];BIGNUM(){clr();return;}
	inline void clr(){memset(s,0,sizeof(s));}
	inline void set(int x){clr();while(x)s[++s[0]]=x%10,x/=10;}
	inline void print(){for(int i=s[0];i>=1;i--)printf("%d",s[i]);}
	friend  BIGNUM operator + (BIGNUM temp_a,BIGNUM temp_b){
		BIGNUM temp_c;int *a=temp_a.s,*b=temp_b.s,*c=temp_c.s;
		c[0]=Max(a[0],b[0])+1;
		for(int i=1;i<=c[0];i++){
			c[i]+=a[i]+b[i];
			if(c[i]>=10)c[i]-=10,c[i+1]++;
		}while(!c[c[0]]&&c[0])c[0]--;
		return temp_c;
	}
	friend BIGNUM operator * (BIGNUM temp_a,BIGNUM temp_b){
        BIGNUM temp_c;int *a=temp_a.s,*b=temp_b.s,*c=temp_c.s;
        for(int i=1;i<=a[0];i++){
			int x=0;
			for(int j=1;j<=b[0];j++){
				c[i+j-1]+=a[i]*b[j]+x;
				x=c[i+j-1]/10;
				c[i+j-1]%=10;
			}c[i+b[0]]=x;
        }c[0]=a[0]+b[0];while(!c[c[0]]&&c[0])c[0]--;
		return temp_c;
	}
	friend BIGNUM Min(BIGNUM temp_a,BIGNUM temp_b){
		int *a=temp_a.s,*b=temp_b.s;
		if(a[0]!=b[0])return a[0]<b[0]?temp_a:temp_b;
		for(int i=a[0];i>=1;i--)if(a[i]!=b[i])return a[i]<b[i]?temp_a:temp_b;
		return temp_a;
	}
};

char s[210];int m,len;
BIGNUM Mul,tot[210][210],num[210],f[210][25],temp;

int main()
{
	freopen("exam4.in","r",stdin);
	freopen("exam4.out","w",stdout);
	scanf("%s",s);scanf("%d",&m);
	len=strlen(s);Mul.set(10);
	for(int i=0;i<len;i++)num[i+1].set(s[i]-'0');
	for(int i=1;i<=len;i++)
	    for(int j=i;j<=len;j++){
			tot[i][j]=tot[i][j-1]*Mul;
			tot[i][j]=tot[i][j]+num[j];
	    }
	for(int i=1;i<=len;i++)f[i][0]=tot[1][i];
	for(int i=1;i<=len;i++){
		for(int j=1;j<i;j++){
			if(j>20)break;
			f[i][j]=f[j][j-1]+tot[j+1][i];
			for(int k=j+1;k<i;k++){
				temp=f[k][j-1]+tot[k+1][i];
			    f[i][j]=Min(f[i][j],temp);
		    }
		}
	}f[len][m].print();
}