POJ 1239-Increasing Sequences

有一串数字，在它们之间加逗号来分隔，使之成为一个上升序列。
要求最后一个数尽可能的小，如果有多个满足要求，则使第一个数尽可能大；如果还有多个，则使第二个最大，依此类推。

感觉这是一道很经典的线性DP题（因为做的太少了）。

思路就是首先保证后一个数尽量大于前一个数，一旦满足条件就去找下一个数。

然后就找到了能满足条件的而且最小的最后一个数，然后我们还需要倒着推使得，前面的数尽量大并且还满足条件。

感觉这道题代码实现极其重要。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
char s[1010],dp[1010];
inline int Judge(int x,int y,int m,int n){
    while(x<=y&&s[x]==0) x++;
    while(m<=n&&s[m]==0) m++;//去除前导0，思路是不是更高精度差不多。。 
    if(x>y) return 0;
    if(m>n) return 1;//如果消失了 
    if((y-x)!=(n-m)) return (y-x)>(n-m);//判断位数 
    for(int i=x,j=m;i<=y&&j<=n;++i,++j){
        if(s[i]!=s[j]) return s[i]>s[j];//从高位到低位扫一遍 
    }
    return 0;
}
int main (){
    while(scanf(" %s",s+1)!=EOF){
        int n=strlen(s+1);
        if(n==1&&s[1]=='0') return 0;
        for(int i=1;i<=n;++i) s[i]-='0';
        dp[1]=1;//dp[i]表示以i结尾，以i-dp[i]+1开头的数字 
        for(int i=2;i<=n;++i){//保证满足条件并且后面的数字尽量小 
            dp[i]=i;//默认如果无法大于前面的任何数就从1开始 
            for(int j=i-1;j>=1;--j){//以j结尾 
                if(Judge(j+1,i,j-dp[j]+1,j)){//判断以j+1开头，i结尾的数能否满足条件 
                    dp[i]=i-j;
                    break;//尽量小，所以一旦找到就退出 
                }
            }
        }
        int end=n-dp[n];//最后一个数字不变
        dp[end+1]=dp[n];//含义变了，表示以i开头，i+dp[i]-1结尾的数字
        //保证满足条件，并且使得前面的数字尽量大
        //因为最后一个数字固定了，所以找后面尽量大，并且小于后面的数 
        for(int i=end;i>=1;--i){ 
            if(s[i]==0){
                dp[i]=dp[i+1]+1;//前导0直接加 
                continue;
            }
            for(int j=end+1;j>i;--j){
                if(Judge(j,j+dp[j]-1,i,j-1)){//跟上面类似 
                    dp[i]=j-i;
                    break;//因为是从后往前扫，所以一旦找到就退出，保证尽量大 
                }
            }
        }
        for(int i=1,fina=i+dp[i]-1;i<=n;++i){
            printf("%d",s[i]);
            if(i==fina&&i!=n) printf(","),fina=i+dp[i+1];
        }
        putchar('\n');
    }
    return 0;
}