记录编号	336110	评测结果	AAAAA
题目名称	[HAOI 2012]添加号	最终得分	100
用户昵称	lingyixiaoyao	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2016-11-02 21:39:27	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL inf=1061109567;
const LL maxn=210;
const LL maxm=30;
const LL mod=7777777;
LL f[maxn][maxm];
LL a[maxn][maxn];
int main()
{
    freopen("purasu.in","r",stdin);freopen("purasu.out","w",stdout);
    //clock_t st=clock();
    string s;cin>>s;LL len=s.size();
    for(LL i=1;i<=len;i++)
    {
        a[i][i]=s[i-1]-'0';
        for(LL j=i+1;j<=len;j++)
        {
            a[i][j]=a[i][j-1]*10+(s[j-1]-'0');
        }
    }
    LL m;scanf("%lld",&m);
    for(LL i=1;i<=len;i++)
    {
        f[i][0]=a[1][i];
        for(LL j=1;j<=m&&j<i;j++)
        {
            f[i][j]=f[j][j-1]+a[j+1][i];
            for(LL k=j+1;k<i;k++)
            {
                f[i][j]=min(f[i][j],f[k][j-1]+a[k+1][i]);
            }
        }
    }
    cout<<f[len][m]<<endl;
    
    return 0;
}