题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1499
题意是说给一个长度最大为80的数字序列，要求划分成多个数字，使数字序列是严格递增的。找出使最后一个数最小的解，多解时输出第一个数最大的，还有多解就输出第二个数最大的，etc。
这题是要构造最优解的dp问题。在只询问最优值是多少的dp问题中，我们往往只记录子问题的值的信息，而在需要构造一个具体解的问题中，我们要保存更多的信息，以帮助我们从最终状态的最优值返回找到一条路径。这里要记录的往往是从前面哪一个状态转移得到当前状态的，即父亲信息。在这个问题中，我没有记录路径信息，具体怎么做的接着看吧。
这个问题中，我们dp数组第一维记录位置信息pos，即“dp到第几位了”，第二维记录如果在这一位后加一个逗号，且前一个逗号在第j+1位后时的是否存在一个满足要求的最优解，有的话，存入最后一个数的值（高精度表示，即第j位到第pos的数字构成的数），否则存INF（高精度的INF）。即是说dp[pos][j]表示：在第一位数字到第pos位数字组成的前缀子序列中，最后一个逗号打在第j位前面（第pos位后的逗号可省略，因为它是子序列最后一位）时是否存在一个满足题意的可行解（== -1？），最优解的最后一个数时多少（dp[pos][j]不等于-1时）。
这显然是一个可以递归定义的子问题。怎么递归呢？如果第j+1位后（即第j位前，位数按从高到低定义）存在一个可行解，即存在一个k>=j+1,使得dp[j+1][k] != -1，且dp[j+1][k] < num[j...pos]。那么dp[pos][j]就存在可行解，且解的最后一位是num[j...pos]（第j位到第pos位构成的数）。
这个转移很好进行，最高位的状态初始化为转移的“内核”，从次高位开始转移，直到最低位。每一位pos枚举前一个“断点”j的位置，判断是否有可行解，有的话更新dp数组。最后我们在dp[0][0...len-1]中找到使dp[0][k]不为-1的k中，使dp[0][k]最小的所有位置k1,k2,...,ks.假设这些dp[0][ki]都取得最小值minans，那么这些解就是满足条件（使最后一个数最小）的可行解。这里所有使dp[0][k]不为-1的k，都是满足序列严格递增的条件的，从我们的转移描述就可以看出。现在我们如何构造满足是第一个数最大，相同时第二个数最大。。。的最优解呢？看下文。
现在我们知道最后一个逗号可以打在第k1,k2,...,ks前面，对这些位置的前一个位置k1+1,k2+1,...,ks+1查看满足dp[ki+1][j]不等于-1的所有j，表示倒数第2个逗号可以到在这些位置j前面，依次递推，这是一个广度优先搜索的过程，意在找出所有使得序列最后一个数取最小值的合法序列中的所有中间状态，成为标记状态。我们从这些任一个状态都可以通过一条仅有标记状态构成的路径回到最后的最优状态。在所有的标记状态中，从前到后贪心的构造一条路径（即第一个数最大，多解时，选第二个数最大，etc）即是最后的结果。
这题的高精度我写的巨恶心，贴上代码会被喷吧。
1 //zzy2012.8.19AC 2 //dp 3 #include<cstdio> 4 #include<cstring> 5 #include<iostream> 6 using namespace std; 7 8 #define sf scanf 9 #define pf printf 10 #define pfn printf("\n"); 11 #define ll long long 12 #define INF (1LL<<62) 13 14 typedef struct{ 15 ll num[10]; 16 ll k; 17 }node; 18 19 char s[81]; 20 node dp[80][80],nn[80]; 21 ll flag[80][80],mm[80],len; 22 23 void ini(){ 24 for(ll i=0; i<80; i++){ 25 mm[i] = 0; 26 nn[i].k = 0; 27 for(ll k=0; k<10; k++) 28 nn[i].num[k] = 0; 29 for(ll j=0; j<80; j++){ 30 dp[i][j].k = 9; 31 for(ll k=0; k<10; k++) 32 dp[i][j].num[k] = 9999999999LL; 33 flag[i][j] = 0; 34 } 35 } 36 } 37 38 void invert(){ 39 char ss[80]; 40 for(ll i=0; i<len; i++) ss[i] = s[i]; 41 for(ll i=0; i<len; i++) s[len-1-i] = ss[i]; 42 } 43 44 ll cmp(node &n1,node &n2){ 45 if(n1.k < n2.k) return -1; 46 if(n1.k > n2.k) return 1; 47 for(ll i=n1.k; i>=0; i--){ 48 if(n1.num[i] < n2.num[i]) return -1; 49 else if(n1.num[i] > n2.num[i]) return 1; 50 } 51 return 0; 52 } 53 54 void copy(node &n1,node &n2){ 55 n1.k = n2.k; 56 for(ll i=0; i<=n1.k; i++) 57 n1.num[i] = n2.num[i]; 58 } 59 60 void add(node &nd,ll d){ 61 nd.num[0] += d; 62 ll i = 0; 63 if(nd.k < 9) nd.num[nd.k+1] = 0; 64 while(i<=nd.k){ 65 if(nd.num[i] >= 10000000000LL){ 66 nd.num[i+1] += nd.num[i] / 10000000000LL; 67 nd.num[i] %= 10000000000LL; 68 } 69 i++; 70 } 71 if(nd.k < 9 && nd.num[nd.k+1] > 0) 72 nd.k ++; 73 } 74 75 node fact(node nd){ 76 while(nd.k>0 && nd.num[nd.k] == 0){ 77 nd.k --; 78 } 79 return nd; 80 } 81 82 void DP(){ 83 for(ll i = len - 1; i>=0; i--){ 84 node temp; 85 temp.k = 0; 86 ll base = 1; 87 for(ll j=0; j<10; j++) temp.num[j] = 0; 88 for(ll j = i; j<len; j++){ 89 if(base == 10000000000LL){ 90 temp.k ++; 91 temp.num[temp.k] = 0; 92 base = 1; 93 } 94 temp.num[temp.k] += (s[j] - '0') * base; 95 base *= 10; 96 node temp2 = fact(temp); 97 if(j+1==len){ 98 copy(dp[i][j], temp2); 99 break; 100 } 101 for(ll k = j+1; k<len; k++){ 102 if(cmp(dp[j+1][k], temp2) == -1){ 103 copy(dp[i][j], temp2); 104 break; 105 } 106 } 107 } 108 } 109 } 110 111 void back_search(){ 112 node min; 113 min.k = 9; 114 for(ll k=0; k<10; k++) 115 min.num[k] = 9999999999LL; 116 for(ll i=0; i<len; i++){ 117 if(cmp(dp[0][i], min) == -1) 118 copy(min, dp[0][i]); 119 } 120 mm[0] = 1; 121 add(min,1); 122 copy(nn[0],min); 123 for(ll i=0; i<len; i++){ 124 if(mm[i] == 0) continue; 125 for(ll j=i; j<len; j++){ 126 if(cmp(dp[i][j], nn[i]) == -1){ 127 flag[i][j] = 1; 128 if(j+1 == len) continue; 129 mm[j+1] = 1; 130 if(cmp(dp[i][j], nn[j+1]) == 1) copy(nn[j+1], dp[i][j]); 131 } 132 } 133 } 134 } 135 136 void print(){ 137 ll stack[80],top = 0,pos = len-1; 138 while(pos >= 0){ 139 node max; 140 max.k = 0; 141 max.num[0] = 0; 142 ll pos2 = 0; 143 for(ll i=pos; i>=0; i--){ 144 if(flag[i][pos] == 0) continue; 145 if(cmp(dp[i][pos], max) != -1){ 146 copy(max, dp[i][pos]); 147 pos2 = i-1; 148 } 149 } 150 stack[top++] = pos2; 151 pos = pos2; 152 } 153 pos = len-1; 154 ll pointer = 0; 155 while(pointer < top){ 156 ll ed = stack[pointer++]; 157 while(pos > ed){ 158 printf("%c",s[pos]); 159 -- pos; 160 } 161 if(ed >= 0) printf(","); 162 } 163 printf("\n"); 164 } 165 166 int main() 167 { 168 while(gets(s)){ 169 len = strlen(s); 170 if(len == 1 && s[0] == '0') break; 171 ini(); 172 invert(); 173 DP(); 174 back_search(); 175 print(); 176 } 177 return 0; 178 }