这么过分一定要写博客
我从昨天下午搞到今天 还复制了题解的代码来自己验证 打开讨论一看 你告诉我是按下标的字典序？？？？？
是我的锅我的锅 怪我不仔细读题 打到怀疑人生 反复WA0分
谢谢你 让我对LIS的认识又加深了呢
倒着来一遍最长下降子序列 然后按照LIS的正常操作出来就是下标字典序最小
/* 你告诉我是下标的字典序最小？？？？？ */ #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define Max(x,y) (x)>(y)?(x):(y) #define Min(x,y) (x)>(y)?(y):(x) #define ll long long #define rg register const int N=10000+5,M=100000+5,inf=0x3f3f3f3f,P=99999997; int n,m,a[N],g[N],d[N],ans=0; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int find(int x){ int l=1,r=ans,mid,an; while(l<=r){ mid=(l+r)>>1; if(g[mid]>x) l=mid+1,an=mid; else r=mid-1; } return an+1; } int main(){ // freopen("in.txt","r",stdin); rd(n); for(int i=1;i<=n;++i) rd(a[i]); for(int i=n;i>0;--i){ int k=find(a[i]); d[i]=k,ans=Max(ans,k); g[k]=a[i]; } rd(m); while(m--){ int x;rd(x); if(x>ans) printf("Impossible "); else { for(int i=1,pre=0;x;++i) if(d[i]>=x&&a[pre]<a[i]){ printf("%d",a[i]); if(x==1) puts(""); else printf(" "); pre=i,--x; } } } return 0; }