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

要看清题啊！！！！