題意很清楚，對(duì)一個(gè)數(shù)字（80位），進(jìn)行劃分，形成若干段，使得這些數(shù)字嚴(yán)格遞增，使得最后一個(gè)數(shù)字最小。如果有重復(fù)，優(yōu)先輸出第一個(gè)數(shù)最大的方案，如果還有重復(fù)，則第二個(gè)數(shù)字最大，以此類(lèi)推～
好吧，以此DP，從前向后掃描可以確定最后一個(gè)數(shù)字最小的方案。為了解決重復(fù)，需要再次用DP構(gòu)造解（以往很多題目都是用貪心直接在第一次DP中構(gòu)造解），即解決這樣一個(gè)自問(wèn)題，在最后一段數(shù)字確定的情況下第一段數(shù)字最大值是多少。做法和第一次DP類(lèi)似，只不過(guò)從后向前掃描。
貼代碼
1 import java.io.*;
2 import java.math.*;
3 import java.util.*;
4 public class Main {
5
6 /**
7 * @param args
8 */
9
10 public static void main(String[] args) throws IOException{
11 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
12 BigInteger arr[]=new BigInteger[100];
13 int path[]=new int[101];
14
15 String str;
16 while(true)
17 {
18 str=in.readLine();
19 Arrays.fill(path,-1);
20 if(str.equals("0")) break;
21 for(int i=0;i<str.length();i++)
22 arr[i]=new BigInteger(str.substring(0, i+1));
23
24 for(int i=0;i<str.length();i++)
25 for(int j=i-1;j>=0;j--)
26 {
27 BigInteger tmp=new BigInteger(str.substring(j+1,i+1));
28 if(tmp.compareTo(arr[j])>0&&tmp.compareTo(arr[i])<0)
29 arr[i]=tmp;
30 }
31 BigInteger target=arr[str.length()-1];
32 Arrays.fill(arr, null);
33 for(int i=str.length()-1;i>=0;i--)
34 if(target.equals(new BigInteger(str.substring(i))))
35 arr[i]=target;
36 for(int i=str.length()-1;i>=0;i--)
37 for(int j=i;j<str.length()-1;j++)
38 {
39 BigInteger tmp=new BigInteger(str.substring(i,j+1));
40 if(arr[j+1]!=null&&tmp.compareTo(arr[j+1])<0&&(arr[i]==null||arr[i].compareTo(tmp)<0))
41 {
42 arr[i]=tmp;
43 path[i]=j;
44 }
45 }
46 int p=0;
47 while(true)
48 {
49 if(path[p]==-1)
50 {
51 System.out.println((p==0?"":",")+str.substring(p));
52 break;
53 }
54 else if(p==0)
55 System.out.print(str.substring(p,path[p]+1));
56 else
57 System.out.print(","+str.substring(p,path[p]+1));
58 p=path[p]+1;
59 }
60
61 }
62
63 }
64
65 }
66