记录编号	477768	评测结果	AAAAAAAAAA
题目名称	[NOI 1996]添加号	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.268 s
提交时间	2017-12-06 18:01:01	内存使用	10.71 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=60,mod=10000;
struct ll{
	int a[maxn],len;
	ll(){
		len=0;
		memset(a,0,sizeof(a));
	}
	ll(int x){
		len=1;memset(a,0,sizeof(a));a[1]=x;
	}
	ll operator +(const ll &B)const{
		ll c;
		c.len=max(len,B.len);
		for(int i=1;i<=c.len;++i){
			c.a[i]=a[i]+B.a[i];
		}
		for(int i=1;i<=c.len;++i){
			if(c.a[i]>=mod){
				c.a[i+1]+=c.a[i]/mod;c.a[i]%=mod;
				if(i==c.len)c.len++;
			}
		}
		return c;
	}
	ll operator *(const int &x)const{
		ll c;
		c.len=len;
		for(int i=1;i<=c.len;++i){
			c.a[i]=a[i]*x;
		}
		for(int i=1;i<=c.len;++i){
			if(c.a[i]>=mod){
				c.a[i+1]+=c.a[i]/mod;c.a[i]%=mod;
				if(i==c.len)c.len++;
			}
		}
		return c;
	}
	bool operator <(const ll &B)const{
		if(len!=B.len)return len<B.len;
		for(int i=len;i>=1;--i){
			if(a[i]!=B.a[i])return a[i]<B.a[i];
		}
		return false;
	}
	void output(){
		printf("%d",a[len]);
		for(int i=len-1;i>=1;--i){
			printf("%04d",a[i]);
		}
	}
}f[205][25],sum[205][205],tmp;
char S[maxn];
int main(){
	freopen("exam4.in","r",stdin);
	freopen("exam4.out","w",stdout);
	scanf("%s",S+1);
	int m;scanf("%d",&m);m++;
	int n=strlen(S+1);
	f[1][1]=ll(S[1]-'0');
	for(int i=1;i<=n;++i){
		sum[i][i]=ll(S[i]-'0');
		for(int j=i+1;j<=n;++j){
			sum[i][j]=sum[i][j-1]*10+(S[j]-'0');
		}
	}
	for(int i=2;i<=n;++i){
		f[i][1]=sum[1][i];
	}
	for(int i=1;i<=n;++i){
		for(int j=2;j<=m&&j<=i;++j){
			f[i][j].len=59;f[i][j].a[59]=1;
			for(int k=1;j-1+k<=i;++k){
				tmp=f[i-k][j-1]+sum[i-k+1][i];
				if(tmp<f[i][j])f[i][j]=tmp;
			}
		}
	}
	f[n][m].output();
	return 0;
}