【bzoj1046】上升序列

时间：2021-10-08 14:36:40

【bzoj1046】上升序列

题意

对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ax2 < … < axm)。那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。任务给出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.

\(1\leq n\leq 10000,1\leq m\leq 1000\)

分析

观察数据范围和时限：10s，支持\(O(n^2)\)

假如不要求最小字典序，那么就是dp傻题了。

最小字典序的处理方法，就是从后往前，倒序处理\(f\)数组。

\(f[i]\)表示以\(i\)为终点的从\(i\)之后出发的最长上升序列的最大长度，\(pre[i]\)表示以\(i\)为\(f[i]\)从哪个位置推过来的。

处理的时候尽可能选后面的。

然后对于每个询问，貌似...

找到第一个\(x\)满足\(f[x]>=Li\)，然后根据\(pre\)输出\(Li\)个就行了？

尝试能不能找到错误。

发现还可能真的有错误。

因为我们的\(f\)是在子序列尽可能长的情况下满足最小字典序的，子序列尽可能长，这可能会存在更短的子序列，而字典序更小。

所以只能从头到尾重新扫一遍就好啦。

遇到一个\(f[x]\geq Li\)，就说明取当前这个有解，且当前这个\(x\)最小，\(Li--\)。

不断输出。

这时候pre根本不需要了。

Extended：

如果要求\(a_i\)字典序怎么办？

方案：按照两个关键字\((a_i,i)\)从小到大排序，和上面的思路相同，要求在后面，逐个尝试。

小结

（1）关于字典序

字典序最小/最大的处理方法：逆序处理。

然后输出就按照自己的记录，或者逐个贪心输出。

代码

#include <cstdio>
#include <cctype>
#include <climits>
#include <algorithm>
using namespace std;

#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)

const int N=16384;
const int MIN=INT_MIN;

int n;
int a[N];

int f[N];
int cnt;

int m;

int rd(void) {
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

void Solve(int c) {
    int lastF=MIN;
    rep(i,1,n)
        if (lastF<a[i]&&f[i]>=c) {
            printf("%d",a[i]);
            if (c==1) printf("\n"); else printf(" ");
            lastF=a[i],c--;
            if (!c) break;
        }
}

int main(void) {
    #ifndef ONLINE_JUDGE
    freopen("bzoj1046.in","r",stdin);
    freopen("bzoj1046.out","w",stdout);
    #endif

    n=rd();
    rep(i,1,n) a[i]=rd();

    per(i,n,1) {
        f[i]=1;
        rep(j,i+1,n)
            if (a[i]<a[j])
                f[i]=max(f[i],f[j]+1);
    }
    cnt=*max_element(f+1,f+n+1);

    m=rd();
    rep(i,1,m) {
        int x=rd();
        if (x>cnt)
            printf("Impossible\n");
        else Solve(x);
    }

    return 0;
}

相关文章