NOIP1999 拦截导弹 导弹拦截问题

先介绍一下偏序关系：偏序是在集合X上的二元关系≤（这只是个抽象符号，不是“小于或等于”），它满足自反性、反对称性和传递性。即，对于X中的任意元素a,b和c，有:自反性：a≤a;反对称性：如果a≤b且b≤a，则有a=b;传递性：如果a≤b且b≤c，则a≤c 。带有偏序关系的集合称为偏序集。令(X,≤)是一个偏序集，对于集合中的两个元素a、b，如果有a≤b或者b≤a，则称a和b是可比的，否则a和b不可比。在X中，对于元素a，如果任意元素b，由b≤a得出b=a，则称a为极小元。一个反链A是X的一个子集，它的任意两个元素都不能进行比较。一个链C是X的一个子集，它的任意两个元素都可比。下面是两个重要定理：定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。其对偶定理称为Dilworth定理：定理2 令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只证明定理1。证明：设p为最少反链个数(1)先证明X不能划分成小于r个反链。由于r是最大链C的大小，C中任两个元素都可比，因此C中任两个元素都不能属于同一反链。所以p>=r。(2)设X1＝X，A1是X1中的极小元的集合。从X1中删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中的元素a1，使得a1<=a2。令A2是X2中极小元的集合，从X2中删除A2得到X3……最终，会有一个Xk非空而X(k+1)为空。于是A1,A2,…,Ak就是X的反链的划分，同时存在链a1<=a2<=…<=ak，其中ai在Ai内。由于r是最长链大小，因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。因此r=p，定理1得证。回过头来看导弹拦截第二问。我们定义偏序关系≤：a≤b表示a出现不迟于b且a的值不小于b的值。这个偏序集的最长反链即最长上升子序列，它的不上升子序列是偏序集的链。由Dilworth定理可知，不上升子序列的最小划分数＝最长上升子序列的长度。

#include<stdio.h>#include<algorithm>using namespace std; const int maxn=1000; intH[maxn],hash[maxn],Rec[maxn];
intmain() { #ifdefjayjayfreopen("in.cpp","r",stdin); #endifintpos=0,MAX,ans1,ans2;while(scanf("%d",&H[pos])!=EOF)pos++; for(inti=0;i<pos;i++)Rec[i]=0,hash[i]=0;Rec[0]=1;for(inti=1;i<pos;i++){MAX=0;for(intj=i-1;j>=0;j--){if(H[i]<=H[j])MAX=max(MAX,Rec[j]);}

Rec[i]=MAX+1;}

MAX=-1;for(inti=0;i<pos;i++){MAX=max(MAX,Rec[i]); }ans1=MAX; hash[0]=1;for(inti=1;i<pos;i++){MAX=0;for(intj=i-1;j>=0;j--){
if(H[i]>=H[j])MAX=max(MAX,hash[j]);}

hash[i]=MAX+1; } MAX=0;for(inti=0;i<pos;i++){MAX=max(MAX,hash[i]); }

ans2=MAX;printf("%dn%dn",ans1,ans2);return 0;

}

爱华网本文地址 » http://www.413yy.cn/a/25101013/159443.html