题意很清楚，对一个数字（80位），进行划分，形成若干段，使得这些数字严格递增，使得最后一个数字最小。如果有重复，优先输出第一个数最大的方案，如果还有重复，则第二个数字最大，以此类推～
好吧，以此DP，从前向后扫描可以确定最后一个数字最小的方案。为了解决重复，需要再次用DP构造解（以往很多题目都是用贪心直接在第一次DP中构造解），即解决这样一个自问题，在最后一段数字确定的情况下第一段数字最大值是多少。做法和第一次DP类似，只不过从后向前扫描。
贴代码
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