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 出了好几...不降(升)序列的 O(nlogn)算法。 2. 不降(升)序列中的方案个数。 (http:...
在最好和最坏情况下的时间复杂度均为O(nlogn),但不稳定...
在最好和最坏情况下的时间复杂度均为O(nlogn),但不稳定的排序算法是()。 A.堆排序 B.快速排序 C.归并排序 D.基数排序_答案解析_2016年_一模/二模/三模/...
算法设计与分析复习题目及答案
D、回溯 B、O(nlogn) 54. 以深度优先方式系统搜索问题解的算法称为 A、分支界限算法 算法 55. 实现最长公共子序列利用的算法是( A、分治策略 B、动态规划法...
算法设计与分析复习题目及答案
( A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 B ) D、数值概率算法 40、背包问题的贪心算法所需的计算时间为( A、O(n2n) B、O(nlogn) C、O(2n)...
lis算法详解
可以使用二分查找高效 地完成,则整个算法时间复杂度下降为 O(nlogn),有了非常...[i] = j; } return size; } 题目分析:同 NYOJ 79 拦截导弹 先解释下...
数据结构(算法)总结
七种常用排序算法的时间复杂度: 最好情况 O( ? ) 冒泡 选择 插入 希尔 n n2 n n1.3 平均情况 O( ? ) n2 n2 n2 nlogn ~ n2 最坏情况 O( ? ) ...
算法11年期末考试卷答案
3. (× )快速排序算法的平均时间复杂度是 O(nlogn),使用随机化快速排 序算法可以将平均时间复杂度降得更低。 4. (× )如果一个问题是 NP 问题,则它一定...
算法设计与分析复习题目及答案
47.背包问题的贪心算法所需的计算时间为( A、O(n2n) B、O(nlogn) C、O(2n) B B、O(nlogn) C、O(2n) D、O(n) )。 D、O(n) 53. 采用贪心算法...
算法设计与分析复习题目及答案
D、回溯 B、O(nlogn) 54. 以深度优先方式系统搜索问题解的算法称为 A、分支界限算法 算法 55. 实现最长公共子序列利用的算法是( A、分治策略 B、动态规划法...
算法设计习题
= Θ(nlogn) 2. 设计一个算法,求给定 n 个元素的第二大元素,并给出算法在最坏情况下使用的比较次 数。 (复杂度至多为 2n-3)算法: Void findsecond(...
更多相关标签:
算法训练 拦截导弹    nlogn算法    美测导弹拦截系统    萨德能拦截多少导弹    萨德能拦截洲际导弹吗    萨德能拦截中国导弹吗    美成功拦截洲际导弹    导弹拦截    

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

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