记录编号	192984	评测结果	AAAAA
题目名称	[HAOI 2012]添加号	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2015-10-13 17:26:58	内存使用	21.46 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=210;
const int maxm=30;
const int mod=7777777;

struct hp
{
    int num[110];
    hp() {memset(num,0,sizeof(num));num[0]=1;}
    void print()
    {
        printf("%d",num[num[0]]);
        for(int i=num[0]-1;i>0;i--) printf("%.4d",num[i]);
        printf("\n");
    }
};

bool operator < (hp a,hp b)
{
    if(a.num[0]!=b.num[0]) return a.num[0]<b.num[0];
    for(int i=a.num[0];i>0;i--)
    {
        if(a.num[i]!=b.num[i]) return a.num[i]<b.num[i];
    }
    return false;
}

bool operator >= (hp a,hp b) {return !(a<b);}

hp operator + (hp a,int b)
{
    a.num[1]+=b;
    int i=1;
    while(a.num[i]>=10000)
    {
        a.num[i+1]+=a.num[i]/10000;
        a.num[i]%=10000;i++;
    }
    while(a.num[a.num[0]+1]!=0) a.num[0]++;
    while(a.num[a.num[0]]==0&&a.num[0]>1) a.num[0]--;
    return a;
}

hp operator + (hp a,hp b)
{
    hp c;c.num[0]=max(a.num[0],b.num[0]);
    for(int i=1;i<=c.num[0];i++)
    {
        c.num[i]+=(a.num[i]+b.num[i]);
        if(c.num[i]>=10000)
        {
            c.num[i+1]+=c.num[i]/10000;
            c.num[i]%=10000;
        }
    }
    while(c.num[c.num[0]+1]!=0) c.num[0]++;
    while(c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--;
    return c;
}

hp operator - (hp a,hp b)
{
    hp c;c.num[0]=a.num[0];
    for(int i=c.num[0];i>0;i--)
    {
        c.num[i]+=(a.num[i]-b.num[i]);
        if(c.num[i]<0)
        {
            c.num[i]+=10000;
            c.num[i-1]--;
        }
    }
    while(c.num[c.num[0]+1]!=0) c.num[0]++;
    while(c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--;
    return c;
}

hp operator * (hp a,int b)
{
    hp c;c.num[0]=a.num[0];
    for(int i=1;i<=c.num[0];i++)
    {
        c.num[i]+=(a.num[i]*b);
        if(c.num[i]>=10000)
        {
            c.num[i+1]+=c.num[i]/10000;
            c.num[i]%=10000;
        }
    }
    while(c.num[c.num[0]+1]!=0) c.num[0]++;
    while(c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--;
    return c;
}

hp operator * (hp a,hp b)
{
    hp c;c.num[0]=a.num[0]+b.num[0];
    for(int j=1;j<=b.num[0];j++)
    {
        for(int i=1;i<=a.num[0];i++)
        {
            c.num[i]+=(a.num[i]*b.num[i]);
            if(c.num[i]>=10000)
            {
                c.num[i+1]+=c.num[i]/10000;
                c.num[i]%=10000;
            }
        }
    }
    while(c.num[c.num[0]+1]!=0) c.num[0]++;
    while(c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--;
    return c;
}

hp f[maxn][maxm];

hp a[maxn][maxn];

int main()
{
    freopen("purasu.in","r",stdin);
    freopen("purasu.out","w",stdout);
    //clock_t st=clock();
    string s;cin>>s;int len=s.size();
    for(int i=1;i<=len;i++)
    {
        a[i][i].num[1]=s[i-1]-'0';
        for(int j=i+1;j<=len;j++)
        {
            a[i][j]=a[i][j-1]*10+(s[j-1]-'0');
        }
    }
    int m;scanf("%d",&m);
    for(int i=1;i<=len;i++)
    {
        f[i][0]=a[1][i];
        for(int j=1;j<=m&&j<i;j++)
        {
            f[i][j]=f[j][j-1]+a[j+1][i];
            for(int k=j+1;k<i;k++)
            {
                f[i][j]=min(f[i][j],f[k][j-1]+a[k+1][i]);
            }
        }
    }
    f[len][m].print();
    //clock_t ed=clock();
    //printf("\nTime used : %.5lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}