题目
BZOJ1046: [HAOI2007]上升序列
题解
这题我WA了三发还是拍出来的你敢信？？
日，，半天才反应过来下标字典序最小是什么意思（这个人脑袋已经昏了）
，贪吧贪吧。每个点开始的lis长度算出来贪着走。原谅我智商捉急还用了bit
noipT2难度
代码
//QWsin
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;const int maxn=10000+10;int a[maxn],dp[maxn],nxt[maxn],t[maxn],n,k;int C[maxn];
#define lowbit(i) ((i)&-(i))
inline void updata(int pos,int val){for(int i=pos;i<=n;i+=lowbit(i)) C[i]=max(C[i],val);
}
inline int query(int pos){int ret=0;for(int i=pos;i;i-=lowbit(i)) ret=max(ret,C[i]);return ret;
}inline void init_data()
{cin>>n;for(int i=1;i<=n;++i) scanf("%d",a+i),t[i]=a[i];sort(t+1,t+n+1);k=unique(t+1,t+n+1)-t-1;for(int i=1;i<=n;++i) a[i]=lower_bound(t+1,t+k+1,a[i])-t;
}inline void solve()
{int L=0;for(int i=n;i>=1;--i){dp[i]=query(k-a[i])+1;updata(k-a[i]+1,dp[i]);L=max(L,dp[i]);}int m,l;cin>>m;while(m--){scanf("%d",&l);if(l > L) puts("Impossible");else{int cnt=0,pre=0;for(int i=1;i<=n&&cnt<l;++i) if(a[i]>pre&&dp[i] >= l-cnt) {if(++cnt==l) printf("%d\n",t[a[i]]);else printf("%d ",t[a[i]]);pre=a[i]; }}}
}int main()
{init_data();solve();return 0;
}