不知道你第一次在 OJ 上看到“拦截导弹”这四个字是什么感觉反正我第一次看到题号 ssl1082 的时候心里想的是这题是不是得用网络流去建模等把题目读完才发现它其实是一道非常典型的线性 DP 图论模型题。题意很简短一套拦截系统可以发射拦截弹但有个硬性限制——后一枚被拦截的导弹高度不能高于前一枚问两件事第一单套系统最多能拦下多少枚导弹第二要把所有导弹都拦下来最少需要多少套系统。就这么两句话背后牵扯出三个经典模型最长不上升子序列、Dilworth 定理、最小路径覆盖。这篇文章我会把这两问从状态设计、二分优化再到图论建模完整拆一遍最后附上可以直接提交的参考代码和我在实际提交中踩过的几个坑。无论你是刚开始刷 DP 的新手还是准备竞赛想系统整理“LIS 家族”题型的选手这篇都值得读完。1. 题目到底在问什么把拦截导弹翻译成算法语言很多人拿到这道题第一反应是“模拟”因为题意描述确实很像一个贪心过程系统拦了一发导弹下一发高度更低就继续拦更高就放弃。但你一旦把“选择哪些导弹来拦”变成“选出来的导弹序列满足什么性质”问题就彻底变了一个模样。1.1 第一问的数学本质是“最长不上升子序列”原题的规则是一枚导弹被拦截之后这套系统再拦下一枚导弹时下一枚高度不能超过当前这一枚。用数学语言说如果我们把导弹按时间顺序排成一排设第 i 枚导弹高度为 h[i]那么同一套系统能拦下的导弹必须满足下标严格递增同时高度满足 h[i] ≥ h[j]i j。换句话说这是在原序列里找一个下标递增、高度不增的子序列。这里有个特别容易被忽略的细节“不高于”意味着高度相等也算合法。所以这个问题叫“最长不上升子序列”也叫“最长非递增子序列”而不是“最长下降子序列”。举个例子序列 [3, 3, 2] 的最长不上升子序列长度是 3因为 3 ≥ 3 ≥ 2 成立但如果你把它当成“最长严格下降子序列”来做答案会变成 2直接丢分。所以第一问的答案本质上就是求一个序列的最长不上升子序列长度。经典解法有两种O(n²) 的动态规划和 O(n log n) 的二分优化。前者适合 n ≤ 5000 的数据后者适合 n 到 1e5 甚至更大的数据。1.2 第二问的本质是“最少链覆盖”第二问稍微绕一点所有导弹都必须被拦截问最少需要多少套系统。每套系统都是一条“下标递增且高度不增”的拦截链。那问题就变成把整个序列里的所有元素划分成若干条这样的链至少要几条在只有十几枚导弹的小数据里你可以靠直觉手工分一分数据一多就必须要有一个理论框架。这里会引出两个视角贪心视角从左到右扫描导弹对每一发导弹在所有“系统最后一发高度不低于当前导弹”的系统里选一个“最后一发高度最小的”系统去接如果没有这样的系统就新开一套。图论视角把每颗导弹看成 DAG 上的一个点i 能接在 j 后面i j 且 h[j] ≥ h[i]就有一条从 j 指向 i 的边。那么一套系统就是一条有向路径最少系统数就是最少路径覆盖数。这两个视角最后都指向同一个结论最少系统数等于原序列的“最长严格上升子序列”长度。注意不是最长不上升子序列是严格上升。这个结论很多人第一次看到都觉得反直觉后面我会专门用一节来解释为什么。1.3 一张表理清三个模型的关系为了不让后面越讲越乱我先把三个模型对应关系列出来题目要求算法模型答案形式一套系统最多拦多少枚最长不上升子序列LNDS一个长度最少需要多少套系统最少链覆盖 / 最小路径覆盖一个数量最少系统数的快速求法最长严格上升子序列LIS一个长度看到这里你应该能感觉到这道题不是孤立的 DP 题它把“序列上的 DP”和“图论里的路径覆盖”打通了。接下来我分两部分先把第一问的两种解法讲透再讲第二问为什么答案是 LIS。2. 第一问的实现从 O(n²) 到 O(n log n)第一问的暴力 DP 是很多人的入门写法但它有一个很深的坑如果你只是机械地写转移方程不理解 dp 数组的语义后面做二分优化时会被边界条件折磨到怀疑人生。2.1 朴素的 O(n²) 动态规划先理解状态转移定义 dp[i] 表示“以第 i 枚导弹作为拦截序列的最后一枚时能形成的最长不上升子序列长度”。那么转移方程就是dp[i] max(dp[j] 1)其中 j i 且 h[j] h[i]初始时每个 dp[i] 1因为单独一枚导弹自己总是可以构成一条长度为 1 的拦截链。计算完所有 dp[i] 后第一问答案是所有 dp[i] 的最大值。举个例子序列 [4, 3, 2, 5, 1]i 1h 4dp[1] 1。i 2h 3前面 4 ≥ 3dp[2] dp[1] 1 2。i 3h 2前面 4 ≥ 2、3 ≥ 2dp[3] dp[2] 1 3。i 4h 5前面没有任何数 ≥ 5dp[4] 1。i 5h 1前面所有数都 ≥ 1dp[5] dp[3] 1 4。所以第一问答案 4对应拦截链 [4, 3, 2, 1]。这个例子也顺便说明了一个要点dp 数组并不是单调递增的你不能像某些区间 DP 那样用一个全局最大值滚动覆盖必须为每个 i 维护独立的状态这也是它需要 O(n²) 的原因。O(n²) 的写法在 n ≤ 2000 时非常稳但一旦数据范围变成 1e5两层循环直接超时。这时候就需要利用“长度和末尾值”来压缩状态也就是下面要讲的二分优化。2.2 二分优化的核心d 数组到底存了什么O(n log n) 优化 LIS 的思路很多人背过代码但真正问一句“d 数组里每个位置存的是什么”能答清楚的人不多。对于本题的最长不上升子序列我们维护一个数组 dd[k] 表示“当前扫描到某个位置时长度为 k 的不上升子序列其末尾元素最大能是多少”。这里“最大”两个字是关键。想想看一个不上升子序列末尾值越大后续越容易接上更小的数所以对同一个长度而言末尾值越大越有优势我们当然希望保留最大的那个。也就是说d 数组是一个递减更准确地说是不增的序列d[1] ≥ d[2] ≥ d[3]...扫描每一枚导弹 x 时我们要做的操作是在 d 里找到第一个严格小于 x 的位置 p。如果找不到说明 x 比当前所有已知不上升子序列的末尾都小或不小于这里要仔细看它可以接在最长的那条链后面形成一条更长的序列所以把 x 追加到 d 末尾如果找到了说明存在一条长度为 p 的不上升子序列它的末尾值小于 xx 可以替换掉 d[p]从而让 d[p] 变得更大这对后续更有利。为什么是“第一个小于 x”而不是“第一个小于等于 x”因为题目允许高度相等。如果 x 等于 d[p]此时 x 不能替换 d[p] 让自己变大但 x 可以接在长度为 p 的子序列后面形成长度为 p1 的序列。用 upper_bound 配合 greater () 就能找到“第一个严格小于 x”的位置误用 lower_bound 会在高度相等时出错。注意如果是“最长严格下降子序列”那就要找第一个小于等于 x 的位置用 lower_bound 配合 greater ()。这一字之差就是 AC 和 WA 的差别。2.3 STL 边界upper_bound 和 lower_bound 怎么配很多人写二分优化时最大的障碍不是算法本身而是 C STL 里 upper_bound 和 lower_bound 的边界感太模糊。我直接给出一张对照表建议收藏目标子序列d 数组方向查找方式最长严格上升子序列递增lower_bound(x)最长不下降子序列递增upper_bound(x)最长严格下降子序列递减lower_bound(x, greater ())最长不上升子序列递减upper_bound(x, greater ())直接说结论可能还是有人记反说一下原理lower_bound 找的是“第一个不满足小于 x 的位置”也就是第一个 ≥ x 的位置upper_bound 找的是“第一个大于 x 的位置”也就是第一个 x 的位置。当比较器反转成 greater 时这两个关系也反转过来。所以严格上升要求不能有相等元素替换掉第一个 ≥ x 的位置用 lower_bound。不下降允许相等x 可以接在等于它的值后面要替换第一个 x 的位置用 upper_bound。严格下降要求不能相等用 lower_bound 配合 greater替换第一个 ≤ x 的位置。不上升允许相等用 upper_bound 配合 greater替换第一个 x 的位置。这张表记住了LIS 家族四个变体你都不会再写错。这里的复杂度是 O(n log n)因为每个元素最多做一次二分查找数组操作也都是常数级别的替换或追加不会出现插入排序那种全体后移的 O(n) 开销。3. 第二问为什么答案是“最长上升子序列”第一问大家一般都能写出来真正的分水岭在第二问。很多人的第一反应是“最少系统数 最长不上升子序列长度”因为一套系统内部高度不增感觉链条越长系统数就越少。这个直觉是错的用一个简单反例就能击穿序列 [1, 2, 3]。这个序列的最长不上升子序列长度是 1因为任意两枚导弹都是上升的根本没可能放进同一套系统而答案显然是 3 套系统每枚导弹单独一套。所以第二问必须要换一个角度想。3.1 先看贪心模拟系统数到底怎么统计我们回到导弹场景模拟一下“上帝视角”的最优拦截。从左到右扫描每一发导弹 x在已有系统里找“最后一发导弹高度不低于 x且这个高度是所有不低于 x 的系统中最小”的那一套让这套系统去拦截 x。如果所有系统的最后一发高度都小于 x说明 x 比当前所有系统的“天花板”都高任何一套都接不住只能新开一套。这个贪心策略不是瞎蒙的它保证不会浪费“高度余量”。比如有两套系统最后一发高度分别是 10 和 8现在来了一发高度 7 的导弹显然应该让 8 那条系统去接把 10 留给后面可能更高的导弹。这就是“能接住的系统里选最后高度最小的”的原因。如果你把每一套系统的“最后一发高度”单独拿出来看会发现它们构成一个严格上升的序列而且这个序列的长度就是当前所需系统数。每次新开一套系统这个序列就多一个元素每次贪心替换实际上是在维护这个严格上升序列的最优形态。这个维护过程和之前求最长严格上升子序列时维护 d 数组的过程完全一致。所以最少系统数 最长严格上升子序列长度。这里顺便说一个很多人问过的点为什么要“严格上升”而不允许相等因为两套系统最后一发高度相等时它们完全可以视为同一套系统的两个阶段高度相等意味着后续能接的导弹集合完全相同没有区分价值。只有当一个高度严格大于另一个时才有必要分属不同系统。3.2 换个视角Dilworth 定理与反链贪心解释虽然直观但总让人觉得“碰巧对”。如果想把第二问上升到理论层面就要引入偏序集的概念。把所有导弹放在一个集合里定义一种偏序关系当且仅当 i j 且 h[i] ≥ h[j] 时我们认为导弹 i 可以排在导弹 j 前面也就是 i “不大于” j 的某个方向。这样定义下一条“链”就是一组互相比起来“可以按时间顺序接续”的导弹也就是同一套系统能连续拦截的序列。一个“反链”就是一组两两不可比的导弹也就是说任取其中两枚都不满足“时间在前且高度不低”的关系。反链具体长什么样在两两不可比的条件下如果 i j那么必须满足 h[i] h[j]也就是高度严格上升。所以反链就是原序列的严格上升子序列。Dilworth 定理的内容是在一个有限偏序集中最少需要多少条链才能覆盖所有元素等于最大反链的大小。把这条定理套到这里立刻得到最少系统数 最长严格上升子序列长度。这个定理的美妙之处在于它把看似是“贪心策略”的结论变成了一个结构性结论你不需要再反复验证某种贪心选择是不是最优的只要题目能抽象成偏序集上的链覆盖答案就是最大反链。这道题考的就是你能不能看出这层转化。3.3 最小路径覆盖建模DAG 上的另一种解法标题里的“最小路径覆盖”指的就是另一条实现路线。我们可以把每个导弹拆成两个点左点 i 和右点 i如果导弹 j 可以接在导弹 i 后面j i 且 h[i] ≥ h[j]就从左点 i 向右点 j 连一条边。这样原问题就变成一个二分图。对于 DAG最小路径覆盖有一个标准公式最小路径覆盖数 顶点数 - 最大二分图匹配数为什么成立简单说每个路径覆盖里有 k 条路径就有 n - k 条连接边。要覆盖所有点连接边越多路径数就越少而连接边之间又要满足“每个点至多有一个前驱、一个后继”的约束这正是二分图匹配的约束。所以最大匹配数越多路径数越少。建图代码核心部分长这样// 左部点i右部点j用 j n 表示 for (int i 0; i n; i) for (int j i 1; j n; j) if (h[i] h[j]) addEdge(i, j n); // i 能接 j然后跑一遍匈牙利算法或者 Dinic得到最大匹配数 maxMatch答案就是 n - maxMatch。那既然有图论做法为什么主流题解都用 LIS 直接算因为匹配算法复杂度至少 O(n³)匈牙利或者 O(n²√n) 级别的网络流而 LIS 只有 O(n log n)。当 n 到 1e5 时图论做法完全不可行LIS 就是唯一现实的选择。我把两种做法对比一下做法复杂度数据范围代码量O(n²) DP 求 LNDS 和 LISO(n²)n ≤ 5000短O(n log n) 二分求 LNDS 和 LISO(n log n)n ≤ 1e5短二分图最大匹配求最小路径覆盖O(n³) 或更高n ≤ 500较长所以最小路径覆盖在这道题里更多是“理解模型”的价值真正提交代码时用 LIS 才是务实的选择。4. 完整参考代码与避坑清单前面讲了这么多模型和原理最终还是要落到能跑通、能 AC 的代码上。这一节我会给出两种完整实现然后重点讲几个我自己的翻车现场。4.1 稳妥的 O(n²) 版本适合 n ≤ 5000这个版本最适合用来理解算法也适合数据范围不大但要求输出方案的场合。代码用固定数组实现思路直白。#include bits/stdc.h using namespace std; const int MAXN 5005; int h[MAXN]; int dpDown[MAXN]; // 以 i 结尾的最长不上升子序列长度 int dpUp[MAXN]; // 以 i 结尾的最长严格上升子序列长度 int main() { int n; if (scanf(%d, n) ! 1) return 0; for (int i 1; i n; i) scanf(%d, h[i]); int ans1 0, ans2 0; for (int i 1; i n; i) { dpDown[i] 1; dpUp[i] 1; for (int j 1; j i; j) { if (h[j] h[i]) dpDown[i] max(dpDown[i], dpDown[j] 1); if (h[j] h[i]) dpUp[i] max(dpUp[i], dpUp[j] 1); } ans1 max(ans1, dpDown[i]); ans2 max(ans2, dpUp[i]); } printf(%d\n%d\n, ans1, ans2); return 0; }这里需要注意dpUp 用的是严格上升也就是 h[j] h[i]对应第二问dpDown 用的是 h[j] h[i]对应第一问。两条转移条件不同一定要分清。4.2 面向大数据范围的 O(n log n) 版本当 n 到 1e5 以上时O(n²) 就没法跑了。这个版本代码很短但每一行背后的意义都要吃透。#include bits/stdc.h using namespace std; int main() { vectorint h; int x; while (scanf(%d, x) ! EOF) h.push_back(x); // 也可能先读 n vectorint dDown; // 不上升子序列优化数组 vectorint dUp; // 严格上升子序列优化数组 for (int v : h) { // 第一问最长不上升子序列 auto it1 upper_bound(dDown.begin(), dDown.end(), v, greaterint()); if (it1 dDown.end()) dDown.push_back(v); else *it1 v; // 第二问最长严格上升子序列 auto it2 lower_bound(dUp.begin(), dUp.end(), v); if (it2 dUp.end()) dUp.push_back(v); else *it2 v; } printf(%zu\n%zu\n, dDown.size(), dUp.size()); return 0; }读入部分写成 EOF 因为有的题目第一行没有 n直接给一串数字如果题目先给 n你就先 scanf 一下 n再用 for 循环读。两种输入格式我在不同 OJ 都见过不要写死。4.3 我在 OJ 上踩过的坑代码看起来简单但越简单的题越容易在细节上翻车。下面几个坑我基本都踩过一遍。第一个坑第二问用了最长不上升子序列。序列 [1, 2, 3] 是经典反例。最长不上升子序列长度是 1但答案明明是 3 套系统。只要第二问写成“求最长下降子序列”这组数据必 WA。第二个坑二分边界写反。第一问求不上升子序列用 upper_bound greater我最早写成 lower_bound greater结果序列 [5, 5] 时答案算出 1实际应该是 2。原因就是 lower_bound 会把相等元素替换掉导致相等的导弹不能排在同一条链里。你把这个例子手推一遍比背十遍边界都记得牢。第三个坑int 和 size_t 比较的警告。d.size() 返回的是无符号数如果你写 for (int i 0; i d.size() - 1; ...)size_t 下溢会让你死循环或越界。最稳妥的方式是不要对 size() 做减法或者转成 int 后再运算。第四个坑多组测试数据时没有清空 vector。很多题目不是单组样例如果你把 vector 定义在局部还好定义在全局就一定要在每组数据开头 clear 一下。我见过有人因为这个原因把第一问答案越算越大定位了半天。4.4 变体与后续扩展“拦截导弹”这类题最大的价值在于它是“LIS 家族”的入口。把这题吃透后至少还能延伸出四个方向如果题目要求“每套系统只能严格下降拦截”第一问变最长严格下降子序列二分用 lower_bound greater第二问变最长不上升子序列二分用 upper_bound greater。正好和原题相反。如果题目要求输出拦截方案O(n²) 版本需要加 pre 数组记录转移来源O(n log n) 版本因为只维护长度不方便直接回溯完整序列通常要换用线段树或者树状数组优化后的 DP 来做路径还原。如果数据范围变成 n 1e5 且还有多组询问可能要把问题上升到“树状数组优化 DP”或者“线段树维护区间最大值”核心仍然是“每个位置继承前方可转移状态的最大值”。如果把导弹换成任务的起止时间、区间调度等问题偏序集上的链覆盖模型依然适用只是偏序关系换了定义。Dilworth 定理这时候才是真正的万能工具。我个人在实际做题中的体会是一道题如果只背代码AC 之后再遇到变体依然会慌但如果你能把“不上升子序列”“最小路径覆盖”“Dilworth 定理”这三层概念在脑子里串成一条线以后再看到类似的序列覆盖题就会一眼认出它在考什么。ssl1082 这道题之所以经典恰恰是因为它用最朴素的背景把这三件事缝在了一起。最后再分享一个小技巧如果你在考场上拿不准第二问到底是求 LIS 还是求 LNDS就直接构造一个反例比如 [1, 2, 3] 或者 [5, 5, 5]手工算一遍。这种一秒钟能验证的小数据比纠结理论推导要可靠得多。把这个习惯保持住你会在很多 DP 题上少走弯路。