9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

导弹拦截nlogn算法



拦截导弹
? 给定N个数
– 求最长的不上升子序列长度 – 求最少有多少个不上升序列能覆盖所有的数, 即求最少覆盖序列。

? N<=10000.

分析
? 设f(i)表示前i个数的最长不上升序列的长度。 则, f(i)=max{f(j)+1},其中j<i and a[j]>=a[i] 这

里0<j<i<=n。 显然时间复杂度为O(n2)。 ? 上述式子的含义:找到i之前的某j,这个数 不比第i个数小,对于所有的j取f(j)的最大值。

优化
? 分析样例 i f 1 2 3 4 5 6 7 8 389 207 155 300 299 170 158 65 1 2 3 2 3 4 5 6

? 这里找j,是在1~i之间进行寻找,那么我们能否快速查找到 我们所要更改的j呢? ? 要能更改需要两个条件: – j<i and a[j]>=a[i] – f(j)尽可能大 ? 以上两个条件提示我们后面的值一定要小于等于前面的值。 因此我们试着构建一个下降的序列。在这个下降的序列中 查找可以更改的f值,使得序列的值尽可能大。

? 具体过程:
i 1 2 3 4 5 6 7 8

389
第 1次 第 2次 389 389

207

155

300

299

170

158

65

207

第 3次
第 4次 第 5次 第 6次 第 7次 第 8次

389
389 389 389 389 389

207
300 300 300 300 300

155
155 299 299 299 299 (由于207<300<389,因此更新) (由于155<299<300,因此更新) 170 170 170 158 158 65

思考?
? 有些同学可能会问: – 对于每个f,为什么只保留一个数值呢? – 而对于该序列,为什么要保留较大的值呢? 1. 再回过头来看方程: f(i)=max{f(j)+1},其中j<i and a[j]>=a[i] 该式子表示找前面的一个最大f的符合条件的j,因此只要保 存符合条件的最大的j就可以了。 2. 在f值相同的情况下,保留较大的数显然更好。因为后面 的数若能跟较小的数构成下降序列也一定能能较大的数 构成下降序列,反之则不一定。例如207与300的f=2,但 207不能与299构成下降序列,而300则可以。
3. 因为生成的序列为有序序列,因此我们可以采用二分查 找的方法很快查找到更新的值,时间复杂度为O(n㏒n)

求导弹的最小覆盖
? 第二问很容易想到贪心法:那就是采取多次求最 长不上升序列的办法,然后得出总次数。 ? 上述贪心法不正确,很容易就能举出反例。 例如: “7 5 4 1 6 3 2” 用多次求最长不上升序列所有为 “7 5 4 3 2”、“1”、“6”共3套系统; 但其实只要2套,分别为: “7 5 4 1”与“6 3 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不可比。 ? 一个反链A是X的一个子集,它的任意两个元素都不能进 行比较。 ? 一个链C是X的一个子集,它的任意两个元素都可比。

定理
? 在X中,对于元素a,如果任意元素b,都有a≤b, 则称a为极小元。 ? 定理1:令(X,≤)是一个有限偏序集,并令r是其 最大链的大小。则X可以被划分成r个但不能再少 的反链。 ? 其对偶定理称为Dilworth定理: 令(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非空而Xk+1为空。于是A1,A2,…,Ak就是X的 反链的划分,同时存在链a1<=a2<=…<=ak,其中ai 在Ai内。由于r是最长链大小,因此r>=k。由于X 被划分成了k个反链,因此r>=k>=p。 (3)因此r=p,定理1得证。

解决
? 要求最少的覆盖,按照Dilworth定理 ? 最少链划分 = 最长反链长度 所以最少多少套系统 = 最长导弹高度上升 序列长度。
? 知道了怎样求最长不上升算法,同样也就 知道了怎样求最长上升序列。 ? 时间复杂度O(n㏒n)。



更多相关文章:
NOIP范围内的DP算法
由于大家都很熟悉了,加上今年来 NOIP 导弹拦截和过河 导弹拦截 过河。 出了好几回,这里不做多说。 特别留意: 1.不降(升)序列的 O(nlogn)算法。 (http:/...
lis算法详解
可以使用二分查找高效 地完成,则整个算法时间复杂度下降为 O(nlogn),有了非常...[i] = j; } return size; } 题目分析:同 NYOJ 79 拦截导弹 先解释下...
RMQ与LCA问题——ST算法
这里有更牛的算法,就是 ST(Sparse Table)算法, 它可以做到 O(nlogn)的预...“导弹拦截” 二、LCA 问题 LCA 问题,即 Least Common Ancestors(最近公共祖先...
算法复习练习题
背包问题的贪心算法所需的计算时间为( A、O(n2n) B、O(nlogn) C、O(2n)...打印出各字符数字和 要大于 n 的所有子集 4、求最长下降序列问题(拦截导弹...
最长上升子序列
[i]; } return ans; } 算法 2: 时间复杂度:(NlogN): 除了算法一的定义...用空格分隔) Output 对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截...
排序算法的O(NlogN)是什么意思(经典算法系列整理5)
排序算法的O(NlogN)是什么意思(经典算法系列整理5)_计算机软件及应用_IT/计算机_专业资料。排序算法 今天才搞清楚排序算法的 O(N*logN)是 什么意思 以前光看了...
三维地形建模技术
析、合理规划及洪水险情预报等.在军事上可用于导航及导弹制导、 作战电子沙盘等...且算法的时间复杂度是 0(1nlogn).此外还缺少细节的局部控制以及难以改变采样的...
算法分析考试题
其中,贪心算法部分只有一重循环影响时间复杂度,其时间复杂度为 O(n):而排序算法的 时间复杂度为 O(nlogn)。因此,综合来看算法的时间复杂度为 O(nlogn)。 c、...
《计算机软件技术基础》复习题和答案
简单选择排序 35.若需在 O(nlogn)的时间内完成对数组的排序,且要求排序是稳定...排序算法的复杂性与排序算法的 (5) 有关。 供选答案: (1): A. 选择 (2...
《数据结构》第08章在线测试
A、希尔排序 B、冒泡排序 C、快速排序 B、选择排序 D、起泡排序 D、直接插入排序 2、下列方法中,___算法的时间复杂度为 O(nlogn)。 A、直接插入排序 B、...
更多相关标签:
导弹拦截 nlogn    算法训练 拦截导弹    导弹拦截算法    经典的nlogn算法    拦截导弹    导弹拦截问题    地对空导弹拦截    拦截导弹 动态规划    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图