注意题目要求的字典序最小是指下标最小
容易想到 $dp$，但是发现正着做不好搞，考虑反过来搞
原本正着做是求最长上升子序列，反过来就变成求最长下降子序列
然后我们就可以求出以每个位置为起点的上升子序列的最大长度
然后直接贪心从前往后枚举即可，复杂度 $O(nm)$
维护最长下降子序列我是用树状数组搞的
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7; int n,m,a[N],b[N],d[N]; int f[N],t[N]; inline void add(int x,int v) { while(x<=n) { if(t[x]<v) t[x]=v; x+=x&-x; } } inline int ask(int x) { int res=0; while(x) res=max(res,t[x]),x-=x&-x; return res; } int main() { n=read(); int c,mx=0; for(int i=1;i<=n;i++) a[i]=d[i]=b[i]=read(); sort(b+1,b+n+1); for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b; for(int i=n;i;i--) f[i]=ask(n+2-a[i]-1)+1,add(n+2-a[i],f[i]),mx=max(mx,f[i]); //本来树状数组求的是小于某个值的范围，为了求大于某个值的范围，把数变成负的然后统一加一个数就行了 m=read(); for(int i=1;i<=m;i++) { c=read(); if(c>mx) { printf("Impossible "); continue; } for(int j=1,p=0;j<=n&&c;j++) if(f[j]>=c&&p<d[j]) p=d[j],printf("%d ",p),c--; printf(" "); } return 0; }