Description

Solution

一开始看成了是子序列的字典序最小，实际上是位置的字典序最小。

先跑一边LIS，然后贪心的选最靠前的LIS够长的序列就行。

Code

由于一开始看错了，代码有点冗余。

const int N = 10010;int a[N], f[N], p[N], g[N], n;void main() {    n = read();    for (int i = 1; i <= n; ++i) a[i] = read();    memset(g, 0x3f, sizeof g);    for (int i = n; i; --i) {        for (int j = i + 1; j <= n; ++j)            if (a[j] > a[i]) {                if (f[j] > f[i]) f[i] = f[j], p[i] = j;            }        f[i]++;        g[f[i]] = i;    }    for (int i = n; i; --i) {        if (g[i] > g[i + 1]) g[i] = g[i + 1];    }    int q = read();    while (q--) {        int x = read();        if (x > n || g[x] == 0x3f3f3f3f)            puts("Impossible");        else {            for (int i = 1, last = 0, j = 1; i <= n && j <= x; ++i)                if (a[i] > last && f[i] >= x - j + 1) {                    printf("%d ", a[i]);                    j++;                    last = a[i];                }            puts("");        }    }}

Note

要看清题啊！！！！