Description
对于一个给定的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.
第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an 第三行一个M，表示询问次数。下面接M行每行一个数L，表示要询问长度为L的上升序列。N<=10000，M<=1000
Output
对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.
6 3 4 1 2 3 6 3 6 4 5
Sample Output
Impossible 1 2 3 6 Impossible
题解
这题很水，但我看错了题目—— 注意是使子序列下标的字典序最小，而不是子序列的字典序最小，所以这题应该比较简单 先从后往前递最长下降子序列，也就是从前往后的最长上升子序列，得到以i开头的最长上升子序列长度f[i]。 然后对于每一次询问len，从1开始扫描，如果f[i]>=len就输出这个数，然后len减1，再往后查找。
代码
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define N 10010int a[N],f[N],g[N];int n,m,len;int find(int x){ int l = 1,r = len,ans; while(l <= r) { int mid = (l+r) >> 1; if(g[mid] > x) { l = mid + 1; ans = mid; } else r = mid - 1; } return ans;}void dp(){ for(int i = n;i >= 1;i--) { int t = find(a[i]); f[i] = t+1; len = max(len,t+1); if(g[t+1] < a[i]) g[t+1] = a[i]; } return;}void work(int l){ int last = 0; for(int i = 1;i <= n;i++) if(f[i] >= l && a[i] > last) { PRintf("%d",a[i]); if(l != 1)printf(" "); last = a[i]; l--; if(!l) break; } printf("/n");} int main(){ int l; scanf("%d",&n); for(int i = 1;i <= n;i++) scanf("%d",&a[i]); dp(); scanf("%d",&m); while(m--) { scanf("%d",&l); if(l > len) printf("Impossible/n"); else work(l); } return 0;}
