Dilworth定理和拦截导弹问题

这道题目是我思考了很久的一道题目,可能是因为我太弱了吧。我们先来分析题目。

第一问

这一问是求一套系统能最大拦截的导弹数量。抽象化后,我们可以得出,其实这一问就是让我们求这个序列中最长的不上升序列。我们先来分析样例输入。

389 207 155 300 299 170 158 65

显然,对于这个序列,他的最长不上升序列是{389,300,299,170,158,65}。那么,我们如何用最佳的算法求出此子序列呢?

贪心策略

我们先设定一个指向变量cursor = 0,这个变量记录当前算法在序列S中的位置。我们再设定一个pos = 0的变量,记录我们子序列H的尾部位置。

如果S[cursor]>H[pos],我们可以直接把S[cursor]置于H的尾部,即H[++pos] = S[cursor]。而如果不是这样,我们则可以在H[0:pos],即0到pos这段区间内,总可以找到第一个小于S[cursor]的的量(事实上,我们可以使用二分搜索来查找这个量,因为序列H是拍好了顺序的),我们就让H[bias] = S[cursor]。反复如此。

为什么要把第一个在序列H中小于S[cursor]的赋为S[cursor]?因为当我们把这个值赋入后,我们后续需要插入数据的时候,便会更容易地加入数字(因为在相同位置下,值越大,后续加入的数字的限制也会缩小),也就会使这个子序列最长。

而如果我们要追求O(n log n)的做法时,便需要二分查找。接下来我来介绍两个函数。

lower_bound(start, end, key, [cmp])

该函数调用后会返回一个有序序列中第一个大于等于(如果有cmp函数传入,那就是另外一回事)key的元素地址。

upper_bound(start, end, key, [cmp])

该函数调用后会返回一个有序序列中第一个大于(如果有cmp函数传入,那就是另外一回事)key的元素地址。

奇怪的是,这两个函数跟字面上的完全不同,upper_bound和lower_bound在没有cmp参数传入的情况下,默认的序列排序情况是一致的。搭配之后,便可以获得O(n log n)的神奇速度。

第二问

Dilworth定理

在一个数字序列中,最大不上升子序列的个数为最大上升子序列的长度。亦而反之。

对于我这种蒟蒻而言,Dilworth定理能帮助到我的只是这句话。我曾经翻阅过很多博客,也翻阅过《组合数学》,我并没有找到易于理解的语句。而在我翻阅到一篇绝世神作之后,我便把我的理解归于这一句话。对于OIer而言,Dilworth最有力的部分便是这句话了。

解题思路

第二问的疑问是求出导弹防御系统的套数,根据Dilworth定理,套数应该等于最大不下降子序列的长度。所以,按照第一问的贪心思路,我们很容易类比出本题求最大不上升子序列的贪心策略。所以,在这里,我便不再赘述。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注