蓝桥杯拦截导弹题解：最长不上升子序列与贪心覆盖

第一次在蓝桥杯算法训练里见到“拦截导弹”这道题我第二问卡了整整一个晚上。样例明明很简单随便一数就能得到“最多拦截6枚最少2套系统”可我一写代码就错不是多判一套就是少判一套。后来看到讨论区有人只说了三个字母LIS。我才明白这道题把两个经典问题藏在了一个背景里最长不上升子序列和最长上升子序列。这篇文章就把这道题的完整拆解、可复现代码和踩坑细节一次讲清楚适合刚接触动态规划、准备蓝桥杯算法训练或刷经典 DP 题的同学参考。1. 题目到底在问什么拆解拦截系统的限制条件1.1 原题描述里最容易被忽略的规则题面通常是这样某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。这种系统有一个缺陷第一发炮弹能够到达任意高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国导弹来袭观测到导弹依次飞来的高度要求计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少需要配备多少套这样的系统。这里有三个关键词依次飞来、不能高于前一发、任意高度。“依次飞来”意味着导弹高度是一个带时间顺序的序列我们只能按时间从前向后选择不能打乱顺序。“不能高于前一发”意味着拦截序列中的高度是非递增的不是严格递减等于是可以的。“第一发炮弹能够到达任意高度”则说明任何一枚导弹都可以作为某套系统的第一个拦截对象不存在“第一枚必须给第一套”的额外限制。经典样例是389 207 155 300 299 170 158 65这套数据第一问答案是6第二问答案是2。6来自389 300 299 170 158 65这是一条长度为6的非递增序列。2来自一种覆盖方式第一套系统拦截389 300 299 170 158 65第二套系统拦截207 155。注意第二套的207和155也是非递增的所以一套系统足以覆盖这两枚导弹。1.2 第一问本质最长不上升子序列如果只看第一问题目等价于在一个长度为 n 的数列中找出一个最长的子序列满足序列中每个元素都不大于前一个元素。这就是经典的最长不上升子序列Longest Non-Increasing SubsequenceLNIS。动态规划的状态设计非常自然。用dp[i]表示以第 i 枚导弹结尾的最长不上升子序列长度。为什么一定要强调“以 i 结尾”因为子序列必须有一个终点把大问题切成小问题时只有知道当前结尾在哪里才能判断下一枚导弹能不能接上去。转移方程是dp[i] max(1, dp[j] 1) 对所有满足 j i 且 h[j] h[i] 的 j初始值dp[i] 1表示只选自己。最终答案取所有dp[i]的最大值。如果在转移时把条件写成h[j] h[i]那求出来的就是最长严格下降子序列和题意不符遇到相同高度就会出错。1.3 用样例手推一遍 dp 表比背代码管用我还是建议拿样例实际推一遍。高度序列下标高度dp[i]说明13891只有自己22072389 20731553389, 207, 15543002389 300207 300 不成立52993389, 300, 29961704389, 300, 299, 17071585389, 300, 299, 170, 1588656389, 300, 299, 170, 158, 65推完这个表你就会发现dp[i]并不一定比dp[i-1]大它只记录“以当前导弹结尾”的最长值。比如下标4的300只能接在389后面长度2下标5的299可以接在300后面长度3。最后答案6。这个过程虽然简单但对理解“子序列可以不连续”很有帮助。2. 为什么第二问不能靠“能拦就拦”解决最少系统数量的本质2.1 一个看似正确但容易写错的直觉算法很多新手看到第二问第一反应是模拟。维护一个数组syssys[i]表示第 i 套系统当前拦截过的最后一枚导弹高度。每来一枚导弹就去现有系统里找一套能拦的拦不了就新开一套。这个思路方向是对的但“找哪一套”很关键。我见过一种错误写法从编号最小的系统开始找哪套能拦就拦哪套。这样会出问题。比如现在有两套系统它们的当前高度分别是400和500新来一枚导弹高度450。如果随便让500那套去拦系统高度会变成450另一套仍然400。后面又来一枚420400那套拦不了450那套也拦不了只能新开系统。但如果一开始让400那套去拦450系统高度变成450另一套还是500后面420可以用500那套拦住就不用新增。结论是在有多个系统都能拦截时要选择当前系统高度尽可能低但又不低于导弹高度的那一套也就是“刚刚好能拦住”的那套。这也是第二问真正的贪心策略每次找sys中第一个不小于当前导弹高度的位置如果没有就新增如果有就把它更新成当前导弹高度。这个策略和最长上升子序列的二分贪心完全等价后面的代码会体现。2.2 用 Dilworth 定理理解“最少系统数 最长上升子序列长度”如果只记结论第二问答案就是最长严格上升子序列长度。这个结论最初看起来非常反直觉一套系统能拦一条非递增链要覆盖全部元素不是应该看最长非递增链吗为什么反而要看最长上升链这里要用到偏序理论里的 Dilworth 定理在有限偏序集中将集合划分为若干条链所需的最少链数等于集合中最大反链的大小。把每个导弹看成一个元素规定两个导弹之间可以“比较”的意思是时间靠前的导弹高度不低于时间靠后的导弹高度即它们可以放进同一套系统的拦截序列中。这样一条“链”就对应一套系统能拦截的一段非递增序列。两个导弹如果时间靠前的高度反而更低也就是出现了严格上升的一对那么它们就是不可比较的必须分到两条不同的链中也就是必须用两套不同的系统去拦。最大反链就是最长的严格上升子序列所以最少链数等于最长严格上升子序列长度。这里必须强调“严格”二字。因为高度相等时5 后面的 5 可以继续被同一套系统拦截两个相同的元素是可以比较的不构成反链只有严格上升的那段序列才强制要求新开系统。2.3 为什么不能直接数最长下降链还有同学会问第二问是不是等于最长下降子序列长度显然不是。最长下降子序列描述的是“一套系统最多能拦多少枚”而第二问描述的是“最少需要几条链才能覆盖全部导弹”。一个是最长链的长度一个是最少链的数量性质完全不同。用样例来看最长下降子序列长度是6而最少系统数是2。如果直接把第一问的答案当第二问误差会非常大。这道题最值得思考的地方就在这里它把“链的长度”和“链的覆盖数”放在同一个背景里逼着你区分这两种不同的统计方式。理解这一点之后遇到类似的“最少机器人覆盖区间”“最少下降序列覆盖数组”等题目都能一眼识别。3. 可复现代码从朴素 DP 到二分贪心3.1 输入处理的坑到底有没有第一行的 N蓝桥杯训练里“拦截导弹”的输入格式在不同版本中不完全一样。有的第一行给出导弹数量 N第二行给出 N 个高度有的不给你 N直接把所有高度放在一行甚至可能分成多行。最稳妥的方式是用流式读取不管换行还是空格都能读完。C 可以这样读vectorint h; int x; while (cin x) h.push_back(x);如果题面明确第一行是 N那就要先读 Nint n; cin n; vectorint h(n); for (int i 0; i n; i) cin h[i];我在某个 OJ 上曾经吃过这个亏题目给的是 N 格式我却用 EOF 循环把所有数字读进来结果把 N 也当成了一枚导弹高度样例能过但提交必 WA。所以动笔前先确认题面。Python 更简单直接读所有数字import sys nums list(map(int, sys.stdin.read().split()))这样不管数字之间是空格还是换行都会变成数组。3.2 第一问O(n^2) 动态规划实现n 不超过 1000 时O(n^2) 完全可以接受。实现如下vectorint dp(h.size(), 1); int ans1 1; for (int i 0; i (int)h.size(); i) { for (int j 0; j i; j) { if (h[j] h[i]) { dp[i] max(dp[i], dp[j] 1); } } ans1 max(ans1, dp[i]); }dp初始化为1保证至少能拦自己。每次枚举前面所有导弹只要前面某个导弹高度不低于当前导弹高度就能接在后面。如果ans1初始为0而数组只有1个元素最后的 max 也能更新成1。为了稳妥初始成1更直观。3.3 第二问用 tail 数组维护“每套系统的当前高度”前面提到正确贪心是维护一个有序数组这里直接用最长严格上升子序列的二分贪心。tail[k]表示长度为 k 的严格上升子序列中最小的末尾元素。遍历每个高度x找到第一个不小于x的位置如果不存在说明可以把x接到当前所有上升子序列的最后面长度增加一即新增一套系统如果存在就用x替换该位置的数表示“用当前高度去更新某个长度的最优末尾”。C 代码vectorint tail; for (int x : h) { auto it lower_bound(tail.begin(), tail.end(), x); if (it tail.end()) { tail.push_back(x); } else { *it x; } } int ans2 tail.size();Python 版本import bisect tail [] for v in nums: pos bisect.bisect_left(tail, v) if pos len(tail): tail.append(v) else: tail[pos] v ans2 len(tail)bisect.bisect_left对应 C 的lower_bound。这个lower_bound的选择是整个第二问最容易错的地方我单独拿出来讲。3.4 为什么是 lower_bound 而不是 upper_bound因为第二问求的是严格上升子序列。维护过程中我们要把等于当前值的旧元素替换掉而不是追加。比如tail [5]再来一个高度5用lower_bound会找到下标0把5替换成5tail长度仍然为1用upper_bound会找到末尾追加一个5tail变成[5, 5]长度2。实际上一套系统完全可以连续拦截两枚高度都为5的导弹因为“不能高于前一发”允许相等。所以第二问答案应该是1upper_bound会错误地给出2。只要把这里想清楚以后看到求最长严格上升子序列就会条件反射地想到lower_bound。完整 C 参考代码#include bits/stdc.h using namespace std; int main() { vectorint h; int x; while (cin x) h.push_back(x); int n h.size(); vectorint dp(n, 1); int ans1 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (h[j] h[i]) { dp[i] max(dp[i], dp[j] 1); } } ans1 max(ans1, dp[i]); } vectorint tail; for (int i 0; i n; i) { auto it lower_bound(tail.begin(), tail.end(), h[i]); if (it tail.end()) tail.push_back(h[i]); else *it h[i]; } cout ans1 \n tail.size() \n; return 0; }4. 同一道题中的两个算法本质上是同一个东西4.1 从“每套系统的末尾高度”看第二问贪心如果你不背 LIS 定理也可以把第二问写成维护系统数组的贪心。数组sys中每个元素是一套系统的当前末尾高度。每来一枚导弹 x在sys中找到第一个不小于 x 的元素找到就更新为 x找不到就push_back(x)。你会发现这个sys的更新逻辑和tail完全一样。也就是说标准贪心模拟和 LIS 的二分贪心并不是两个不同的方法而是同一个数学结构的两面。理解了这一点以后你甚至可以自己推导遇到“最少需要几条下降链覆盖数组”这类问题直接想象一个有序的系统高度数组然后套用二分即可。4.2 相等边界的实战意义再来感受一下相等边界。假设全部导弹高度都一样比如5 5 5 5。第一问答案是4因为一套系统从头拦到尾高度始终是5没有上升。第二问答案是1因为不需要第二套。用tail跑一遍第一个5进来tail[5]第二个5进来lower_bound找到位置0并替换tail还是[5]后面同理。最后 tail.size()1。这就是对的。但如果用了upper_bound每一枚5都会追加tail最后变成[5,5,5,5]长度4错得非常离谱。我建议所有选手拿到这题后都手动测一下5 5 5 5和1 2 3 4这两组极端数据。前者验证相等处理后者验证最长上升子序列长度是不是等于 n。如果你的程序两边都能过边界基本没问题。4.3 从二维偏序的角度看覆盖问题如果只把“拦截导弹”当作一道 DP 题会错失很多收获。仔细想想每个导弹有两个属性出现下标 i 和高度 h[i]。一套系统能够同时拦截 i1 和 i2需要满足 i1 i2 且 h[i1] h[i2]。这正是二维平面上的“前一个点在后一个点的左上方”关系。要求用最少的“单调折线”覆盖所有点本质是一个二维偏序下的最小链划分问题。Dilworth 定理把它转化为最大反链问题而这里的反链就是严格上升的点列。很多竞赛题比如“最少用多少个单调栈覆盖数组”“最少用多少条机器人路径覆盖点集”底层都是同一个模型。所以这道蓝桥杯训练题虽然写起来不长但它连接的数学背景非常广。5. 我在训练中踩过的坑以及给初学者的调试建议5.1 样例能过但交上去 WA先检查输入格式这是最常见的一个坑。蓝桥杯版本的“拦截导弹”有些题面会先给出 N有些不会。如果你不管三七二十一用while (cin x)遇到先给 N 的数据会把 N 也读进导弹高度数组导致答案完全不对。反过来如果题面不给 N你却先用cin n那就会把第一个高度当作 N然后少读一个数。我的习惯是每次做题前先看输入描述里有没有明确写“第一行为一个整数 N”有这个字眼就先读没有就直接 EOF 循环。5.2 空数据、单数据、全相等数据的自测方法本地测试时可以先准备几个小用例空数组程序应该输出0和0或者直接退出单个导弹5第一问1第二问1全相等5 5 5第一问3第二问1严格递增1 2 3第一问1第二问3严格递减3 2 1第一问3第二问1。这几个用例覆盖了大多数边界。用它们去跑你的代码能在几分钟内发现低级的逻辑错误。5.3 如果第二问 WA怎么排查第二问如果 WA我建议先别急着怀疑 Dilworth 定理而是打印tail每一步的变化。比如用例5 1 6 2 4正确的 tail 变化是5 1 1 6 1 2 1 2 4长度3所以答案3。你可以对照自己的输出看是在哪一步多了一个元素或少了一个元素。如果发现相等高度也被追加进去了那就是lower_bound写成了upper_bound。如果 tail 乱序可能是你插入时没有保持有序或者用了push_back后没有排序。记住tail 始终是严格递增的因为每次替换都是把一个较大的值换成较小的值不会破坏递增性。5.4 给初学者的总结这一题可以浓缩成两句话第一问求的是“最长不上升子序列长度”用 DP第二问求的是“最长严格上升子序列长度”用二分贪心。前者的答案是“最长链的长度”后者的答案是“最小链覆盖数”。别把它们弄混遇到相等高度时记得用lower_bound输入尽量用流式读取剩下的就是多写多调。这道题非常适合作为算法竞赛里动态规划和贪心思想的转折点把它吃透后面很多题目都会轻松很多。我后来再看到“导弹拦截”这四个字第一反应已经不是那组样例数据了而是 Dilworth 定理带来的那个反直觉瞬间你要覆盖所有下降链答案却藏在最长的上升链里。这种“绕一下”的美感大概就是算法竞赛最吸引人的地方。建议你也把这题收藏下来等学到树状数组之后再回头看看能不能把第一问也优化到 O(n log n)那种连贯的进阶感会非常有趣。