NOIP1999 拦截导弹 导弹拦截问题

自己都觉得自己有点奇葩!搞完ACM比赛之后,又开始搞NOI,呵呵,不过玩自己喜欢的挺好的!问题描述  某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
  输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式  一行,为导弹依次飞来的高度
输出格式  两行,分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数
样例输入389 207 155 300 299 170 158 65
样例输出6
2
题目分析:导弹拦截是一个经典问题:求一个序列的最长不上升子序列,以及求能最少划分成几组不上升子序列。第一问是经典动态规划,第二问直接的方法是最小路径覆盖,但是二分图匹配的复杂度较高,我们可以将其转化成求最长上升子序列,其最大值即等于不上升子序列的最小划分数。这就涉及到组合数学中偏序集的Dilworth定理。(第二问的贪心方法其实就是这个定理的证明过程)
先介绍一下偏序关系:偏序是在集合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;

}




[NOIP1999]拦截导弹 导弹拦截问题

  

爱华网本文地址 » http://www.aihuau.com/a/25101013/159443.html

更多阅读

苹果iPhone6怎么拦截骚扰电话 iphone7 骚扰电话拦截

苹果iPhone6怎么拦截骚扰电话——简介苹果iPhone6如何拦截骚扰电话,苹果iPhone6怎么拉黑骚扰广告电话,现在经常有些广告电话或者直接是机器播放声音的电话打进入,怎么把这些电话进行拉黑呢。苹果iPhone6怎么拦截骚扰电话——工具/原料

手机总是收到垃圾短信怎么办 苹果拦截短信插件

手机总是收到垃圾短信怎么办——简介我们经常会碰到这种情况,总是受到保险啦,卖房什么的垃圾短信 ,下面介绍一种方法十分简单,就把那些垃圾短信排除啦手机总是收到垃圾短信怎么办——工具/原料智能手机ios 或者安卓系统手机总是收到

遇到呼死你软件骚扰电话怎么拦截 苹果怎么拦截呼死你

相信呼死你软件大家都对其略有耳闻,它可是名符其实的臭名昭著。遭遇了呼死你的用户每天能够接到成千上万个骚扰电话,可是人们虽然对它恨得牙痒痒,但依旧不知道哪种方法能够彻底的拦截“呼死你”,不过不要再担心了,今天我就来与大家

360手机卫士怎么拦截骚扰电话和短信? 华为 360卫士骚扰拦截

360手机卫士怎么拦截骚扰电话和短信?——简介电话和短信很多,如何过滤掉这些垃圾骚扰的电话和短信呢?让我们的生活多一分清静!360手机卫士怎么拦截骚扰电话和短信?——工具/原料电话360手机卫士软件360手机卫士怎么拦截骚扰电话和短信?—

弹窗广告怎么去掉 如何拦截弹窗广告 如何拦截弹窗广告

弹窗广告怎么去掉 如何拦截弹窗广告——简介相信大家对于弹窗广告也是十分反感的,在这个广告肆意横行的年代,无论软件、还是上网浏览网页时,总会弹出一些烦人的广告,对此我们该如何拦截以优化我们的视觉呢?以下就是具体的实现方法。弹窗

声明:《NOIP1999 拦截导弹 导弹拦截问题》为网友沫雅萱分享!如侵犯到您的合法权益请联系我们删除