记录编号	531876	评测结果	AWWWW
题目名称	124.[NOI 1996]添加号	最终得分	20
用户昵称	wire	是否通过	未通过
代码语言	C++	运行时间	0.064 s
提交时间	2019-05-21 20:26:19	内存使用	21.29 MiB

    /*边 界 值 ：dp [p， 0 ]： = NUM[0， p]
    Dp[p,x ]表 示前 p个 数 字 中 添 上 x个 加 号 后 得 到 的 最 小 值 。
    NUM[x，y ]表 示数 字 串 从 x 到 y 的 数 */
    #include<bits/stdc++.h>
    #define maxn 1000
    #define inf 0x3f3f3f3f
    using namespace std;
    int n;
    char c[maxn];
    int dp[maxn][maxn];
    int num[maxn][maxn];
    int m;
    int NUM(int x,int y)
    {
    	if(num[x][y]!=-1)
    	{
    		return num[x][y];
    	}
    	unsigned long long sum=0;
    	for(int i=x;i<y;i++)
    	{
    		sum=sum*10+c[i]-'0';
    	}
    	num[x][y]=sum;
    	return sum;
    }
    int DP(int p,int x)
    {
    	if(dp[p][x]!=-1)
    	{
    		return dp[p][x];
    	}
    	if(x==0)
        {
            dp[p][0]=NUM(0,p);
            return dp[p][0];
        }
        dp[p][x]=inf; 
        for(int k=p-1;k>=x;k--)
        {
            dp[p][x]=min(dp[p][x],DP(k,x-1)+NUM(k,p));
    /*
    即前 p 坐标的数字添加 x 个加号的最小值 = min { 前 p 坐标的数字添加 x 个加号 或 递推之后与从 x到y数的和}
    */
    	}
    	return dp[p][x];
    }
     
    int main()
    {
    	freopen("exam4.in","r",stdin);
    	freopen("exam4.out","w",stdout);
    	int i=0;
        while(~scanf("%s",c))
        {
        	i++;
            memset(dp,-1,sizeof(dp));
            memset(num,-1,sizeof(num));
            cin>>m;
            n=strlen(c);
            cout<<DP(n,m); 
        }
        return 0;
    }