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; }