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)。



更多相关文章:
在最好和最坏情况下的时间复杂度均为O(nlogn),但不稳定...
在最好和最坏情况下的时间复杂度均为O(nlogn),但不稳定的排序算法是()。 A.堆排序 B.快速排序 C.归并排序 D.基数排序_答案解析_2016年_一模/二模/三模/...
...的排序算法在最坏情况下的计算时间下界为O(nlogn)。...
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中,最坏情况下计算时间可以达到O(nlogn)的是 (21) ,该算法采用的设计方法...
...的排序算法在最坏情况下的计算时间下界为O(nlogn)。...
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中,在最坏的情况下,计算时间可以达到O(nlog...
...的排序算法在最坏情况下的计算时间下界为O(nlogn)。...
以关键字比较为基础的排序算法在最坏情况下的计算时间下界为O(nlogn)。下面的排序算法中,在最坏的情况下,计算时间可以达到O(nlog...
NOIP范围内的DP算法
由于大家都很熟悉了,加上今年来 NOIP 导弹拦截和过河 导弹拦截 过河。 出了好几回,这里不做多说。 特别留意: 1.不降(升)序列的 O(nlogn)算法。 (http:/...
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最...
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是( )。 A.堆排序 B.起泡排序 C.快速排序 D.希尔排序 _答案解析_2016年_一模/二模/三模/联考_...
算法分析与设计题
有两个 10 制的大整数(不少于 30 位) ,设计一分治算法,以 O(nlogn) 时间...? 输入:导弹依次飞来的高度(不大于30000 的正整数) , 输出:最多能拦截多少...
lis算法详解
可以使用二分查找高效 地完成,则整个算法时间复杂度下降为 O(nlogn),有了非常...[i] = j; } return size; } 题目分析:同 NYOJ 79 拦截导弹 先解释下...
nlogn的最长上升子序列(pascal语言)
nlogn的最长上升子序列(pascal语言)_经管营销_专业资料。nlogn的最长上升子序列(pascal语言)B. 最长不下降子序列的 O(n*logn)算法分析如下: 设 A[t]表示序列中...
更多相关标签:

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

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