dp[i][j]表示前j个分了i次的最小值。
因为最坏的情况是：
第1个数是一位，第二个是2位，依次递推
1，2，3，4，5，6，7，8，9，10，11，12，13，14，15；
求最后一个数最小，最后一位最多是个15位的数。所以long long型足够了。
当最后的数确定下来最小的结果时，就要让前面的数尽量大了。只需让dp[k][len-1]（分了k次）只需让k尽量小就可以。
zoj上可以AC，但这不能，请大家多多指教。提出宝贵意见！
#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define INF (1LL<<55)
typedef long long lld;
char c[100];
long long dp[100][100];
long long path[100][100];
long long sum[100][100];
void dfs(lld k,lld p)
{
    lld temp=path[k][p];
    if(temp!=0)
    dfs(k-1,temp-1);
    for(lld i=temp;i<=p;i++)
            printf("%c",c[i]);
    printf(",");
}
int main()
{
    lld i,j,k,len;
    while(cin>>c)
    {
        len=strlen(c);
        if(len==1&&c[0]=='0')break;
        memset(path,-1,sizeof(path));
        memset(sum,-1,sizeof(sum));
        for(i=0;i<len;i++)
        {
            sum[i][i]=(long long)(c[i]-'0');
            for(j=i+1;j<len;j++)
            {
                sum[i][j]=sum[i][j-1]*10+(long long)(c[j]-'0');
                if(sum[i][j]>=INF)break;
            }
        }
        for(i=0;i<=len;i++)
            for(j=0;j<=len;j++)
                dp[i][j]=INF;
        for(i=0;i<len;i++)
        {
            if(sum[0][i]==-1)break;
            dp[1][i]=sum[0][i];
            path[1][i]=0;
        }
        for(k=2;k<=len;k++)
            for(i=1;i<len;i++)
                for(j=i;j>0&&sum[j][i]!=-1;j--)
                {
                    if(dp[k][i]>sum[j][i]&&sum[j][i]>dp[k-1][j-1])
                    {
                        dp[k][i]=sum[j][i];
                        path[k][i]=j;
                    }
                }
        long long ans=INF;
        for(i=len;i>=1;i--)
            if(dp[i][len-1]<=ans)
                ans=dp[i][len-1],k=i;
        if(k!=1)
        dfs(k-1,path[k][len-1]-1);
        for(i=path[k][len-1];i<len;i++)
            printf("%c",c[i]);
        printf("\n");
    }
}

• Re:相当另类的算法 (2111) whr2290 2012-10-11 15:48:09
  • Re:相当另类的算法 (36) whr2290 2012-10-11 15:52:09