这道题数据有点水了($n \le 10^4$,$m \le 10^3$),我给出一个 $O(nm)$ 的做法吧。
1.预处理
$dp_i$ 表示以 $i$ 为开头的最长上升序列的长度。
$O(n \log n)$ 求最长上升子序列:
设 $f_i$ 为最长上升子序列长度为 $i$ 的 $j$,$a_j$ 的最小值。
容易发现 $f$ 数组是单调增的。
二分求最后一个小于 $a_i$ 的 $f_j$,$dp_i=j+1$。
接着更新 $f_{dp_i}$。
这道题就是把数组倒过来,求最长下降子序列。
一点不同,这里的 $f$ 数组是单调降的。
有一个办法,把 $f$ 数组倒过来。
但 $f$ 数组长度会变。巧妙的解决办法就是,把 $f_i$ 存到 $f_{10000-i+1}$,$dp_i=10000-j+1$。($n \le 10000$)。
2.求长度为 $L_i$ 的最长上升子序列
这道题妙就妙在要你求下标最小。肯定是选 $a_1$,接着选第一个大于 $a_1$ 的,直到选到第 $L_i$ 个。
万一选不到 $L_i$ 个怎么办?看 $a_2$ 呗。$a_2$ 也不行呢?看 $a_3$。会超时。
我们不是预处理了 $dp_i$ 吗?拿来用啊!
假设还要选 $x$ 个,如果 $dp_i < x$ 或者 $a_i \le last$(其中 $last$ 是上一次选的数,初始为零),那就不选 $i$。
如果这么处理了,还选不到 $L_i$ 个,就说明找不着了。
3.代码加注释
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10010],b,dp[10010],f[10010],p,ans[10010];
int main(){
scanf("%d",&n);
for(int w=1;w<=n;w++)scanf("%d",&a[w]);
dp[n]=1,f[10000]=a[n];//10000-1+1=10000
for(int w=n-1;w;w--){
if(a[w]>f[10000])dp[w]=1,f[10000-dp[w]+1]=max(a[w],f[10000-dp[w]+1]);//a[w]太大,用不着找了,直接是1
else{
int k=upper_bound(f+1,f+10000+1,a[w])-f;k=10000-k+1;//前面的都是0,只有10000-t+1到10000有值,等于从10000-t+1找到10000
dp[w]=k+1,f[10000-dp[w]+1]=max(a[w],f[10000-dp[w]+1]);//已经变成10000-k+1,直接抄上去,别忘了加一,更新f数组
}
}
scanf("%d",&m);
for(int w=1;w<=m;w++){
scanf("%d",&b),p=0;//p=0别忘了!
int k=0;//上一次选的数,初值为比什么数都小的0
for(int x=1;x<=n&&b;x++)
if(a[x]>k&&dp[x]>=b)k=a[x],b--,ans[++p]=a[x];//能选w,只要选b-1个数了
if(b)printf("Impossible\n");//如果选完b应该是0,不是0说明没选完
else{
for(int w=1;w<=p;w++)printf("%d ",ans[w]);
printf("\n");
}
}
return 0;
}