poj-1239(递推关系）好难

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 int dp[];

 char str[];

 int n;

 bool isbiger (int x1,int y1,int x2,int y2) {//判断x1-y1字符串与x2-y2字符串的大小

     while (str[x1]==''&&x1<=y1) x1++;

     while (str[x2]==''&&x2<=y2) x2++;

     if (x1>y1)  return ;

     if (x2>y2)  return ;

     int n1=y1-x1; int n2=y2-x2;

     if (n1>n2) return ;

     if (n2>n1) return ;

     for (;x1<=y1;x1++,x2++) {

         if (str[x1]>str[x2])  return ;

         else if (str[x1]<str[x2])  return ;

     }

     return ;

 }

 int main ()

 {

     char _end[]="";

     while (gets(str+)&&strcmp(str+,_end)!=) {

         int n=strlen(str+); dp[]=;

         for (int i=;i<=n;i++) {//第一次dp --dp[i](1-i字符串构成递增序列，最后一个字符串的最小长度)

             dp[i]=i;

             for (int j=i;j>=;j--) {

                 if ( isbiger(j,i,j-dp[j-],j-) ) {

                     dp[i]=i-j+;

                     break;

                 }

             }

         }

         int len=n-dp[n];

         dp[len+]=dp[n];

         int i;

         for (i=len;i>=&&str[i]=='';i--) //第二次dp--利用已知最后一位的最小值反推前面的最大值

             dp[i]=dp[i+]+;// 前导为零即使加上最后一个字符的大小不会改变

         for (;i>=;i--) {

             for (int j=len;j>=i;j--) {

                 if ( isbiger (j+,j+dp[j+],i,j) ) {//dp[i]-(从i-n字符串中) 第一个字符串的最大值

                     dp[i]=j-i+;

                     break;

                 }

             }

         }

         i=;

         while (i<=n) {

             int j=i+dp[i];

             for (;i<j;i++)

                 printf ("%c",str[i]);

             if (i<=n)

                 printf (",");

         }

         printf ("\n");

     }

     return ;

 }