拦截导弹(牛客)
不消说 第一个问就是求最长不下降子序列
这个题的重点是第二个问
Dilworth定理：偏序集的最少反链划分数等于最长链的长度
简而言之就是要求最长上升子序列(严格上升的)
点击查看代码
#include
#include
#include
using namespace std;
int n,maxn,ans1,ans2,f[1000001],a[1000001];
int lowbit(int x){return x&-x;}
void add(int x,int c){
for(int i=x;i<=maxn;i+=lowbit(i)) f[i]=max(f[i],c);
}
int query(int x){
int res=0;
for(int i=x;i>=1;i-=lowbit(i)) res=max(res,f[i]);
return res;
}
int main(){
while(scanf("%d",&a[++n])!=EOF) maxn=max(maxn,a[n]);
n--;
for(int i=n;i>=1;i--){
int q=query(a[i])+1;
add(a[i],q);
ans1=max(ans1,q);
}
printf("%d\n",ans1);
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++){
int q=query(a[i]-1)+1;
add(a[i],q);
ans2=max(ans2,q);
}
printf("%d\n",ans2);
}