很多打算法竞赛的同学第一眼看到“拦截导弹”这四个字都以为又是一道最长上升子序列的裸题结果做到第二问就卡住了到底要配多少套系统为什么有人说用贪心有人说用最小路径覆盖还有人说本质上就是最长上升子序列我当年第一次做这道题的时候也在这绕了很久。今天就把这道经典题彻底拆开从动态规划到 Dilworth 定理再到二分图最小路径覆盖一次讲透。这篇文章适合刚学完 LIS 想进阶的选手也适合想弄明白“第二问为什么等于最长上升子序列”的朋友。1. 先看懂题两个问题对应两个完全不同的模型1.1 原题规则与输入输出这道题的原型在很多 OJ 上都有题目描述基本是这样某国开发了一套导弹拦截系统这套系统有一个特点——第一发炮弹可以打到任意高度但从第二发开始每一发炮弹都不能高于前一发炮弹。也就是说一套系统拦截下来的导弹高度必须构成一个非递增序列。某天雷达接收到了敌国来袭的一串导弹高度因为系统还在试用阶段所以想知道用一套系统最多能拦下多少枚导弹如果要防空导弹全部拦下来又最少需要多少套系统经典的样例输入是这样的389 207 155 300 299 170 158 65对应输出6 2第一问答案是 6因为最长的不上升子序列可以是389 300 299 170 158 65第二问答案是 2意思是最少要两套系统配合才能把 8 枚导弹全部拦截。输入格式没有提前告诉你导弹数量而是以 EOF 结束所以读入时用while (cin x)这种写法最稳妥。导弹高度的范围在不同版本里不太一样通常是不大于 30000 的正整数导弹数量一般是 1000 左右但也有数据加强版会到 10 万级别这直接决定了你该用哪种做法。1.2 第一问的本质最长不上升子序列第一问“一套系统最多能拦多少枚导弹”本质上就是在高度序列里找一个最长的子序列使得这个子序列从前往后满足前一项 后一项。注意这里一定是也就是允许相等。题目原话说“每一发炮弹都不能高于前一发”所以相等高度照样可以拦。这个细节看起来小事实际写转移方程的时候等号漏掉就等于送了一组数据。后面我会专门讲这个等号陷阱。1.3 第二问的本质用最少的不上升子序列覆盖整个序列第二问“全部拦下来最少需要几套系统”翻译过来就是把整个序列切成若干个不相交的子序列每个子序列都是不上升的问最少能切成几段。这就不再是单纯 DP 的事了。把“段”看成链条把“高度比较关系”看成偏序关系这其实是一个组合数学里非常经典的问题最小链划分。很多题解直接说第二问就是最长上升子序列长度但没有讲清楚为什么导致初学者只能背结论。我建议你先把贪心模拟的直觉建立起来再去看 Dilworth 定理最后再补上二分图最小路径覆盖的视角这样整条逻辑线才是完整的。2. 第一问的 DPO(n^2) 打法与等号细节2.1 状态设计设dp[i]表示以第i枚导弹作为末尾时能形成的最长不上升子序列长度。为什么以“末尾”作为状态因为子序列的延续性只看末尾元素。当扫描到新的一枚导弹时它理论上可以接在前面任何一枚高度不低于它的导弹后面接了之后新的末尾就是当前导弹的高度。我们要的就是所有可能接法里的最大值。转移方程写出来是这样的dp[i] max(1, dp[j] 1) 其中 j i 且 a[j] a[i]初始化时每枚导弹单独构成一个长度为 1 的子序列所以dp[i]至少为 1。2.2 O(n^2) 的参考代码导弹数量在 1000 左右时O(n^2) 完全够用代码也非常直观#include bits/stdc.h using namespace std; const int N 1005; int a[N], dp[N]; int main() { int n 0; while (cin a[n 1]) n; int ans 0; for (int i 1; i n; i) { dp[i] 1; for (int j 1; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } cout ans \n; return 0; }这个代码的核心就一句话扫描所有在i前面的导弹只要它的高度能“压住”当前导弹就尝试把它的最长长度接过来再加一。2.3 为什么相等高度必须算上我曾经亲眼见过一个学弟把a[j] a[i]写成了a[j] a[i]结果样例都过不了。为什么因为题目说的是“不高于”不是“低于”。如果两枚导弹高度都是 100同一套系统完全可以先拦第一枚 100再拦第二枚 100因为这并没有高于前一发。如果你写成严格大于那 100 就不能接在 100 后面最长不上升子序列的长度就会被低估。记住一句话不上升 非递增 允许相等 用转移。这个等号问题不只在第一问出现第二问的“严格上升”里也有一个反向的等号陷阱后面会专门说。3. 第二问的贪心直觉给系统排一张“值班表”3.1 模拟规则每一枚导弹到底交给谁拦先别急着上定理我们用一个最朴素的思路来想手里现在有几套系统每套系统最后一次拦截的高度是多少。新来一枚导弹时我们要决定让哪套系统去拦。如果所有系统的最后一次拦截高度都低于当前导弹那任何一套系统都没法拦只能新开一套系统。如果存在至少一套系统能拦选哪一套答案是选那套当前能拦截、且最后一次拦截高度最小的系统。举个例子现在有两套系统一套最后拦截高度是 100另一套是 200来了一个高度为 120 的导弹。第一套100拦截不了第二套200能拦。但如果后面又来了一个高度 180 的导弹呢这时候如果刚才让 200 那套去拦 120它现在的高度就变成 120180 就拦不了了可如果刚才新开一套拦 120让 200 那套留着180 就能被 200 拦下。所以正确的贪心不是“能用就用”而是“能用弱系统就不用强系统”把强的留到后面。3.2 实现思路与朴素代码用数组last[]记录每套系统当前最后一次拦截的高度初始为空。对每个导弹a[i]在last中找最小的那个满足last[k] a[i]的值。找到了就把last[k]更新为a[i]。找不到说明所有系统都拦不住新增一套系统last里加入a[i]。朴素写法时间复杂度 O(n * m)m 是系统数量最坏情况下 O(n^2)vectorint last; for (int i 1; i n; i) { int pos -1; for (int k 0; k (int)last.size(); k) { if (last[k] a[i]) { if (pos -1 || last[k] last[pos]) { pos k; } } } if (pos -1) last.push_back(a[i]); else last[pos] a[i]; } cout last.size() \n;这段逻辑写出来之后你会发现last数组始终是升序的。每次替换的都是第一个大于等于当前高度的位置替换后它变小了但依然不小于它前面的值同时不大于它后面的值有序性不会被破坏。这个性质很重要后面 O(n log n) 优化就靠它。3.3 贪心正确性的直觉证明为什么“选能拦截且高度最小的”一定对可以用交换论证来想假设某次最优方案里当前导弹被系统 A 拦截而系统 B 是“能拦当前导弹且高度更小”的那一套并且系统 B 在这个导弹之后要拦截某个高度较高的导弹。如果把当前这次拦截从 A 换给 B再把 A 和 B 后续的任务对调一下你会发现所有后续拦截依然合法因为 B 的高度比 A 更小B 换成拦当前这个更低的导弹只会更轻松A 保留了更高的拦截能力去执行 B 原本要执行的高高度任务也不会更难。系统总数没有增加所以贪心选择不会比最优方案差。这个交换论证在思路层面已经足够严格的证明网上能搜到我就不贴一整篇了。4. 第二问背后的定理Dilworth 与最长上升子序列4.1 从系统数量到最小链划分现在把问题抽象一下。给导弹按出现顺序编号 1 到 n两枚导弹 编号 i 在 编号 j 前面如果a[i] a[j]我们就说 i 可以“覆盖” j也就是它们可以被同一套系统先后拦截。每一套系统拦截的导弹序列都满足“编号递增且高度非递增”这在一套偏序关系里就是一条链。第二问要求用最少的系统数覆盖所有导弹也就是求这个偏序集的最小链划分数量。这里需要引入一个组合数学的经典结论——Dilworth 定理在有限偏序集中最小链划分的数量等于最长反链的长度。反链的意思是集合里任意两个元素都不能相互覆盖。这个定理直接回答了我们的问题最少系统数 最长反链长度。4.2 反链恰好是严格上升子序列那在这个题目场景里反链长什么样两个导弹 i、ji 在 j 前面不能相互覆盖意味着不满足a[i] a[j]也就是必须有a[i] a[j]。如果整个集合任意两枚导弹都满足这个关系那这个集合按编号排下去高度就是严格递升的。所以最长反链就是最长严格上升子序列。看到这里你应该就明白了第二问的答案 最长严格上升子序列LIS的长度。第一问是最长不上升子序列允许相等第二问是最长严格上升子序列不允许相等。两个问题表面上都是“找子序列”实际一个是一个是方向完全相反。这也是这道题最迷惑人的地方。4.3 一个特别容易踩的等号陷阱正因为第二问要求的是“严格上升”所以你在写 LIS 的转移代码时判断条件必须是a[j] a[i]绝不能写成a[j] a[i]。我举个极端的例子来验证100 100 60第一问最长不上升子序列是100 100 60长度 3一套系统就能全拦下——因为 100 不高于 10060 不高于 100完全合法。第二问如果用非严格上升来算会得到100 100长度为 2答案就是 2但实际答案显然是 1。只有严格上升子序列的长度才是1也就是根本不存在一高一低严格递增的两枚导弹。这个例子直接说明了第二问为什么必须用严格上升。很多 OJ 上的题解不会解释这个差异直接把 LIS 模板贴上去你要是跟着抄一遍遇到相等高度的数据就翻车了。所以记住第一问用第二问用这两者的区别就是整道题的题眼。5. 换个视角最小路径覆盖与二分图最大匹配5.1 把问题画成一张 DAG第二问除了贪心和 Dilworth 定理之外还有一个图论视角把每枚导弹看成图上的一个节点如果编号 i 在编号 j 前面且a[i] a[j]就从 i 向 j 连一条有向边。这条边的含义是同一套系统拦截完 i 之后还能继续拦截 j。因为所有边都是从编号小的点指向编号大的点这个图不可能有环是一张 DAG有向无环图。那么一套系统拦截的一串导弹就是这张图里的一条路径。第二问就变成了用最少的路径覆盖所有节点这就是经典的 DAG 最小路径覆盖问题。5.2 拆点建二分图DAG 最小路径覆盖有一个现成的结论把每个节点 u 拆成左部点 u_L 和右部点 u_R原图中的每条边 u - v 变成左部点 u_L 连向右部点 v_R 的一条边然后在这个二分图上求最大匹配答案就是最小路径覆盖数 总点数 - 最大匹配数这个结论的直觉解释很简单一开始 n 个节点各自算一条路径也就是 n 条二分图里每匹配一条边等价于把两条本来独立的路径首尾相接路径总数就减少 1。我们希望路径数最少就要匹配数最大。5.3 匈牙利算法实现n 在 1000 左右时用匈牙利算法跑最大匹配非常轻松。完整代码如下#include bits/stdc.h using namespace std; const int N 1005; int a[N]; vectorint g[N]; int match[N]; bool vis[N]; bool dfs(int u) { for (int v : g[u]) { if (!vis[v]) { vis[v] true; if (match[v] 0 || dfs(match[v])) { match[v] u; return true; } } } return false; } int main() { int n 0; while (cin a[n 1]) n; for (int i 1; i n; i) { for (int j i 1; j n; j) { if (a[i] a[j]) { g[i].push_back(j); } } } int ans1 0; vectorint dp(n 1, 1); for (int i 1; i n; i) { for (int j 1; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans1 max(ans1, dp[i]); } int matchCnt 0; for (int i 1; i n; i) { memset(vis, 0, sizeof(vis)); if (dfs(i)) matchCnt; } cout ans1 \n; cout n - matchCnt \n; return 0; }建边这里再提醒一次一定要用a[i] a[j]。如果两个导弹高度相等它们是可以被同一套系统拦截的省略这个等号会多算系统数量。5.4 为什么这个视角值得学可能有人会说“最小路径覆盖这么麻烦第二问直接输出 LIS 长度不就好了吗”确实这题的数量答案用 LIS 一行就出来了。但我觉得最小路径覆盖视角还是值得认真学一遍原因有三个。第一它帮你建立了“序列问题可以映射到图上”的思维方式。很多算法题表面是数组本质是图你多一个视角就多一条路。第二有些变体题问的不只是数量而是要把每一套系统拦截了哪些导弹输出出来。这时候 LIS 只能告诉你答案是多少但没法直接告诉你方案而最小路径覆盖可以。只要记录下匹配边然后找到所有没有“入边”的节点作为路径起点沿着匹配边一路走到底就能还原出每条路径。第三Dilworth 定理和最小路径覆盖在后面的组合优化题里经常交叉出现比如任务调度、偏序集上的覆盖问题打好这个基础不亏。6. 数据加强版用贪心加二分做到 O(n log n)6.1 第一问的 nlogn维护“每个长度的最大末尾值”如果数据范围加大到 n 100000上面 O(n^2) 的 DP 就会超时。这时候要用经典 LIS 贪心 二分优化但不上升版本和上升版本的写法有微妙区别。维护一个数组dd[len]表示当前扫描到某个位置时长度为len的不上升子序列的最大末尾值。为什么维护最大末尾因为同样长度的子序列末尾值越大越容易接上后面更小的导弹对后续扩展越有利。这个d数组本身是单调递减的长度越长末尾值不可能更大。处理新导弹x时我们在d里找第一个严格小于x的位置。为什么是“严格小于”因为不上升序列允许相等所以一个末尾值为x的序列也能接上当前这个x我们要找的是真正“接不住”的那个位置来替换。手写二分版参考代码int len 0; for (int i 1; i n; i) { int l 1, r len, pos len 1; while (l r) { int mid (l r) 1; if (d[mid] a[i]) { pos mid; r mid - 1; } else { l mid 1; } } if (pos len 1) { d[len] a[i]; } else { d[pos] a[i]; } }最终len就是最长不上升子序列长度。这里二分的查找目标是“第一个小于x的位置”和标准 LIS 里“第一个不小于x的位置”正好相反容易写混建议大家像我一样把判断条件写清楚。6.2 第二问的 nlogn维护系统数组第二问的 O(n log n) 其实和上面第一问的 nlogn 是“镜像”关系。还记得第三节那个last数组吗它始终升序每来一个导弹x找第一个 x的位置lower_bound找到就替换成x找不到就push_back(x)最终last.size()就是最少系统数。这其实就是严格 LIS 的 nlogn 模板也再次验证了 Dilworth 定理第二问 严格 LIS。注意这里的二分方向因为last是升序要找第一个 x的正好是 C 的lower_bound而不是第一问里那个“找第一个小于 x”。两个数组一个递减一个递增二分目标完全相反别套错模板。下面给出第二问的 STL 写法vectorint last; for (int i 1; i n; i) { auto it lower_bound(last.begin(), last.end(), a[i]); if (it last.end()) last.push_back(a[i]); else *it a[i]; } cout last.size() \n;这段代码跑完last里的元素个数就是最少系统数。6.3 严格与不严格的分界lower_bound 还是 upper_bound这个细节我单独拉出来说因为它真的很容易出错。求最长严格上升子序列时我们要保证递增是严格的所以相等元素不能接在同一个子序列里。对当前元素x应该找第一个 x的位置替换也就是lower_bound。求最长非严格上升子序列时相等元素可以接。此时找的是第一个 x的位置替换也就是upper_bound。一句口诀严格用 lower_bound不严格用 upper_bound。但具体到拦截导弹这道题第一问是不允许上升非递增第二问是严格上升两个都不是标准 LIS 的“裸形态”所以别只背口诀最好把d数组的含义从头理一遍再下手。7. 完整 AC 代码与实战避坑清单7.1 推荐提交版本全 nlogn 写法如果你不确定 OJ 的数据范围直接用下面这份最稳n 在 100000 以内都能跑#include bits/stdc.h using namespace std; const int N 100005; int a[N], d1[N], d2[N]; int main() { int n 0; while (cin a[n 1]) n; int len1 0; int len2 0; for (int i 1; i n; i) { int x a[i]; // 最长不上升子序列d1 递减找第一个 x 的位置 int l 1, r len1, pos len1 1; while (l r) { int mid (l r) 1; if (d1[mid] x) { pos mid; r mid - 1; } else { l mid 1; } } d1[pos] x; if (pos len1 1) len1; // 最少系统数 最长严格上升子序列last 升序找第一个 x 的位置 int L 1, R len2, pos2 len2 1; while (L R) { int mid (L R) 1; if (d2[mid] x) { pos2 mid; R mid - 1; } else { L mid 1; } } d2[pos2] x; if (pos2 len2 1) len2; } cout len1 \n; cout len2 \n; return 0; }这份代码是我在 OJ 上实际提交过多次的版本输入为空时不会误输出东西二分边界也测试过几组边界数据大家可以放心参考。7.2 几组用来本地验证的边界数据我每次写完新版本都会拿这些数据验证输入第一问第二问说明300 200 10031最简单递减序列1 2 313严格上升序列每枚都要新系统100 100 6031检验两个等号陷阱389 207 155 300 299 170 158 6562标准样例5 4 1 3 232反链藏在中间拿最后一组手动验一下5 4 1 3 2最长不上升子序列是5 4 3 2长度 4等等3 在位置 42 在位置 55 4 1不对5 4 3 2中 4 在位置 23 在位置 42 在位置 543 且 32合法长度 4。第二问最少系统数。LIS 严格上升是1 3长度 2还能 1 2 长度 2所以 2。验证一下贪心系统15 4 1系统23 2刚好 2 套。对。7.3 我踩过的坑和要提醒你的话最后整理几个实战中容易出问题的地方读入别写死。有些同学喜欢先读 n 再读数组但这题的输入就是不告诉你 n一个while (cin x)最省事。二分数组的下标从 1 开始还是从 0 开始全程保持一致。我上面的代码下标从 1 开始pos初值设成len 1这个初值别改成 0否则无论如何都会被当成“找到了替换位置”导致新增长度永远不发生。第二问千万别顺手用了lower_bound在递减数组上。网上有些 LIS 模板是给严格上升写的直接拿来做第二问没问题但你要清楚它求的到底是什么如果你拿它去求第一问那就是在乱撞。最小路径覆盖的匈牙利算法每次增广前都要清空vis数组。这个错误我犯过不止一次导致匹配数偏大路径数偏小答案错得莫名其妙。写到这里我自己又把这道题从 DP 到贪心到 Dilworth 到二分图匹配完整过了一遍。回头看拦截导弹之所以经典就是因为它把几个看似不相关的知识点串在同一条线上一个等号区分了两种模型一个定理连接了组合数学和图论一种 LIS 模板能在不同问法下换着花样用。如果你第一次做的时候被第二问绕晕了别灰心把这篇的推理顺序自己再推一遍尤其是“反链就是严格上升子序列”那一步想通之后你会觉得这道题的内核其实非常简单。