题解 P2215 【[HAOI2007]上升序列】

颜伟业_C_Asm · 2018-01-05 16:56:23 · 题解

首先楼下的都用的O(nlogn)，其实这个题的数据范围是可以用暴力O(n^2)的。我是先用n^2求出从各项开始往后的最长上升序列长度，然后在询问时首先看看l如果大于已知最长的上升序列的话那么Impossible，否则就从头开始找。如果从这个地方开始的最大长度比l大时，就输出这个数并且记录下这个数（因为以后找到的数都要比这个数小），然后我们已经找到了一个，就将l-1，然后接着重复上述步骤直到整个序列都被找出也就是l=0。因为我们一直是从前开始找的，所以字典序肯定是最小的。

代码如下：

    #include<cstdio>
    using namespace std;
    int ints[10001];//序列
    int dp[10001];//从此处开始的最长上升序列长度
    int get(){//读入优化
        int n;
        char c;
        while(1){
            c=getchar();
            if(c>='0'&&c<='9')break;
        }
        n=c-'0';
        while(1){
            c=getchar();
            if(c>='0'&&c<='9'){
                n=n*10+c-'0';
            }
            else{
                return(n);
            }
        }
    }
    int main(){
        int n=get();
        for(int i=1;i<=n;i++){
            ints[i]=get();
            dp[i]=1;//把结果都初始化为1
        }
        int imax=1;//整个序列中的最长的上升序列长度
        for(int i=n-1;i>=1;i--){//暴力n^2求最长上升序列
            int maxn=1;
            for(int j=i+1;j<=n;j++){
                if(ints[j]>ints[i]){
                    if(dp[j]+1>maxn){
                        maxn=dp[j]+1;
                    }
                }
            }
            dp[i]=maxn;
            if(maxn>imax)imax=maxn;
        }
        int m=get();
        for(int i=0;i<m;i++){
            int l=get();
            if(l>imax||l<=0){//如果l比整个序列的最长上升序列都要长，肯定是找不到的
                printf("Impossible\n");
            }
            else{
                int tmp=l;//要找的长度
                int last=-1;//上一个找到的数，接下来找到的数都应比这个大
                for(int j=1;j<=n;j++){
                    if(dp[j]>=tmp&&ints[j]>last){
                        printf("%d ",ints[j]);
                        last=ints[j];//记录下找到的数作为上一个
                        tmp--;//找到了一个就减去1
                        if(tmp==0)break;
                    }
                }
                printf("\n");
            }
        }
        return(0);
}