poj-1239(递推关系）好难

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 using namespace std;
 6 int dp[100];
 7 char str[100];
 8 int n;
 9 bool isbiger (int x1,int y1,int x2,int y2) {//判断x1-y1字符串与x2-y2字符串的大小
10     while (str[x1]=='0'&&x1<=y1) x1++;
11     while (str[x2]=='0'&&x2<=y2) x2++;
12     if (x1>y1)  return 0;
13     if (x2>y2)  return 1;
14     int n1=y1-x1; int n2=y2-x2;
15     if (n1>n2) return 1;
16     if (n2>n1) return 0;
17     for (;x1<=y1;x1++,x2++) {
18         if (str[x1]>str[x2])  return 1;
19         else if (str[x1]<str[x2])  return 0;
20     }
21     return 0;
22 }
23 int main ()
24 {
25     char _end[]="0";
26     while (gets(str+1)&&strcmp(str+1,_end)!=0) {
27         int n=strlen(str+1); dp[1]=1;
28         for (int i=2;i<=n;i++) {//第一次dp --dp[i](1-i字符串构成递增序列，最后一个字符串的最小长度)
29             dp[i]=i;
30             for (int j=i;j>=1;j--) {
31                 if ( isbiger(j,i,j-dp[j-1],j-1) ) {
32                     dp[i]=i-j+1;
33                     break;
34                 }
35             }
36         }
37         int len=n-dp[n];
38         dp[len+1]=dp[n];
39         int i;
40         for (i=len;i>=1&&str[i]=='0';i--) //第二次dp--利用已知最后一位的最小值反推前面的最大值
41             dp[i]=dp[i+1]+1;// 前导为零即使加上最后一个字符的大小不会改变
42         for (;i>=1;i--) {
43             for (int j=len;j>=i;j--) {
44                 if ( isbiger (j+1,j+dp[j+1],i,j) ) {//dp[i]-(从i-n字符串中) 第一个字符串的最大值
45                     dp[i]=j-i+1;
46                     break;
47                 }
48             }
49         }
50         i=1;
51         while (i<=n) {
52             int j=i+dp[i];
53             for (;i<j;i++)
54                 printf ("%c",str[i]);
55             if (i<=n)
56                 printf (",");
57         }
58         printf ("
");
59     }
60     return 0;
61 }
抓住青春的尾巴。。。