> 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:相当另类的算法 (36) whr2290 2012-10-11 15:52:09