題目大意:給出一個序列,求出字典序最小的長度為k的上升序列。
思路:先随便搞搞求出一個數組f,表示從i開始最長的上升序列的長度。然後貪心的往後找,能放在目前位置就放。
CODE:
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 10010
#define INF 0x3f3f3f3f
using namespace std;
int src[MAX];
int f[MAX],max_length[MAX];
int cnt,asks;
bool cmp(int a,int b)
{
return src[a] > src[b];
}
int ans[MAX];
int main()
{
cin >> cnt;
for(int i = 1; i <= cnt; ++i)
scanf("%d",&src[i]);
for(int i = cnt; i; --i) {
int p = lower_bound(f + 1,f + cnt + 1,i,cmp) - f;
max_length[i] = max_length[f[p - 1]] + 1;
f[p] = i;
}
int length = 0;
while(f[length + 1]) ++length;
cin >> asks;
for(int x,i = 1; i <= asks; ++i) {
scanf("%d",&x);
if(x > length) puts("Impossible");
else {
int temp = x,last = -INF;
for(int i = 1; i <= cnt; ++i)
if(max_length[i] >= temp && src[i] > last) {
printf("%d",src[i]);
last = src[i];
--temp;
if(temp) putchar(' ');
else {
puts("");
break;
}
}
}
}
return 0;
}