Mayflyyh
Mayflyyh
MayFlyyh's Blog
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;
}
本文链接:http://www.mayflyyh.com/archives/276
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      POJ 1239-Increasing Sequences
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

MayFlyyh's Blog

POJ 1239-Increasing Sequences
有一串数字,在它们之间加逗号来分隔,使之成为一个上升序列。 要求最后一个数尽可能的小,如果有多个满足要求,则使第一个数尽可能大;如果还有多个,则使第二个最大,依此类推。 感…
扫描二维码继续阅读
2018-07-15