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.
Input
第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an 第三行一个M，表示询问次数。下面接M行每行一个数L，表示要询问长度为L的上升序列。
Output
对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.
Sample Input
6
3 4 1 2 3 6
3
6
4
5
3 4 1 2 3 6
3
6
4
5
Sample Output
Impossible
1 2 3 6
Impossible
1 2 3 6
Impossible
HINT
数据范围
N<=10000
M<=1000
题解
为了保证所谓字典序“最小”。可以倒着做一边最长下降子序列。然后对于每个问题枚举统计答案即可。有时候想太多反而会错。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define inf 1<<30
using namespace std;
int n,m,a[10005];
int f[10005],stk[10005],top,maxf;
void init()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
}
int erf(int x)
{
int l=0,r=top,mid,w;
while(l<=r)
{mid=(l+r)>>1;
if(stk[mid]<=x) r=mid-1;
else {w=mid; l=mid+1;}
}
return w;
}
void predp()
{
int i,w;
f[n]=1; stk[0]=inf;
stk[1]=a[n]; top=1;
for(i=n-1;i>0;i--)
{w=erf(a[i]);
f[i]=w+1;
if(w==top) {top++; stk[top]=a[i];}
else stk[w+1]=max(stk[w+1],a[i]);
}
for(i=1;i<=n;i++) maxf=max(maxf,f[i]);
}
void work()
{
scanf("%d",&m);
int i,j,x,now;
for(i=1;i<=m;i++)
{scanf("%d",&x);
if(x>maxf) puts("Impossible");
else
{now=-inf;
for(j=1;j<=n;j++)
{if(f[j]>=x&&a[j]>now)
{if(x==1) {printf("%d\n",a[j]); break;}
else
{x--; printf("%d ",a[j]); now=a[j];}
}
}
}
}
}
int main()
{
init(); predp();
work();
return 0;
}