luogu1020 导弹拦截

题目描述

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度(雷达给出的高度数据是 $\le 50000$的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

$1$行,若干个整数(个数 $\le 100000$)

输出格式

$2$行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例输入

389 207 155 300 299 170 158 65

样例输出

6
2

分析

数据增强版导弹拦截,卡掉了$O(n^2)$算法。

第一问直接最长不降子序列,主要看第二问。

对于第二问,之前普遍使用的算法是贪心,每次找能拦截当前导弹的最低的系统拦截,拦不下来则再开一套系统。这个贪心的正确性是显然的,直接枚举的复杂度是$O(n^2)$,但寻找最低的系统时可以用二分查找优化到$O(n\log n)$。

但此题还有另外一种做法:直接输出最长上升子序列。如果这个做法也是对的,那么贪心解法是否是最长上升子序列的另类解法?它的原理是什么?

考虑对最长上升子序列这个问题进行图论建模:对于每个数,向它右边大于它的数连边。那么我们建了一张DAG,最长上升子序列即为DAG中的最长链。

根据Dilworth定理,最长链=最小反链覆盖。在这张图中,反链即为不升子序列,所以最长上升子序列可以转化为原图最少能划分成几条不升子序列,然后用导弹拦截的贪心做法解决。

代码

// 假装有代码


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论