Dilworth定理的證明：http://www.cnblogs.com/nanke/archive/2011/08/11/2134355.html

感覺難理解。有空研究。

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int INF=100005; int n,a,f1[INF],f2[INF],top1,top2; void find(int l,int r) {if(l>r){f1[l]=a;top1=max(top1,l);return;}int mid=(l+r)/2;if(f1[mid]>=a)find(mid+1,r);else find(l,mid-1);//// } int main() {f1[0]=INF;while(scanf("%d",&a)==1){if(a<=f1[top1])f1[++top1]=a;else find(1,top1);if(a>f2[top2])f2[++top2]=a;else{int k=lower_bound(f2+1,f2+top2+1,a)-f2;f2[k]=a;}}printf("%d\n%d",top1,top2);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Narh/p/8511953.html

總結(jié)

以上是生活随笔為你收集整理的洛谷1020导弹拦截的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。