poj 1239dp(Increasing Sequences로 분할)

제목: 길이가 80보다 크지 않은 숫자열을 정하고 숫자열을 쉼표로 구분해야 한다. 각 자열이 표시하는 숫자는 엄격하게 단조롭게 증가하고 구분 후 마지막 숫자가 가장 작다는 것을 보증한다.여러 가지 상황의 마지막 열이 나타내는 숫자와 동시에 구분된 첫 번째 숫자가 가장 큰 것을 취하고 첫 번째 숫자도 같으면 구분된 두 번째 숫자를 보면 숫자 앞에 0, 즉 000001이 1을 나타낼 수 있다.
사고방식: 다음 dp로 가서 마지막 숫자의 최시간이 얼마인지 구하면 이 dp는 비교적 이해하기 쉽다. dp[i]는str[0~i]라는 꼬리가 마지막 하위 꼬리의 최시간 마지막 꼬리를 만족시키는 것을 나타낸다. 즉str[dp[i]~i]가 마지막 꼬리이다.이어서 앞으로 두 번째 dp에서 마지막 숫자가 가장 적은 상황에서 앞의 열을 최대한 크게 충족시킬 것을 구한다.여기에는 0에 대한 처리에 주의해야 한다.

#include <cstdio>
#include <cstring>
#define max(a,b) ((a)>(b)?(a):(b))
#define N 85
char str[N],dp[N],p[N],len;
int cmp(int a,int b,int c){//   str[a,b-1] str[b,c]   
    int i=a,j=b;
    while(i<b-1 && str[i]=='0')
        i++;
    while(j<c && str[j] == '0')
        j++;
    if(b-i < c-j+1)
        return -1;
    else if(b-i > c-j+1)
        return 1;
    for(;i<b;i++,j++){
        if(str[i] < str[j])
            return -1;
        else if(str[i]>str[j])
            return 1;
    }
    return 0;
}
int zero(int len){
    int i;
    for(i = len;i>=0;i--){
        if(str[i] != '0')
            return i;
		p[i] = strlen(str)-1;//               0  
	}
    return -1;
}
int main(){
	freopen("a.txt","r",stdin);
    while(scanf("%s",str) && strcmp(str, "0")){
        int i,j;
        len = strlen(str);
        dp[0] = 0;
        for(i = 1;i<len;i++){//   dp
            for(j = i;j>0;j--)//           
                if(cmp(dp[j-1],j,i)<0)
                    break;
            dp[i] = j;
        }

        p[dp[len-1]] = len-1;
        len = dp[len-1];//       （      ）
        if((j=zero(len-1)) && j==-1){//      0（               0  ）
            printf("%s
",str);
            continue;
        }
        for(i = j;i>=0;i--)
            for(j = len;j>i;j--)//          
                if (cmp(i, j, p[j])<0) {
                    p[i] = j-1;
                    break;
                }
        for(i = j = 0;i<strlen(str);i++){//  
            if(i<=p[j])
                putchar(str[i]);
            if(i==p[j] && i!=strlen(str)-1){
                j = i+1;
                putchar(',');
            }
        }
        printf("
");
    }
    return 0;
}