我第一次做《拦截导弹》这道题时思路非常天真从第一发开始往下扫能连成一串下降的就当成一套系统遇到上升就再开一套。样例倒是能过可一上洛谷就被加强数据教做人了。后来我才意识到这道题根本不是“模拟拦截过程”它问的是两个非常标准的算法模型第一问要你求一套系统最多能拦截多少发本质上是最长不上升子序列第二问要你求至少需要几套系统本质上是一个贪心加链覆盖的模型而且它和最长上升子序列的长度有着惊人的关系。这篇文章适合刚接触动态规划和贪心、或者刷了不少题但总把这两类方法混着用的读者我会从最朴素的 O(n²) DP 一直讲到 O(n log n) 的二分写法再给你看第二问的贪心为什么能一步到位。1. 题意还原一套系统到底在做什么1.1 从“不高于上一发”到“不上升子序列”先看题面描述某系统拦截导弹时第一发可以拦截任意高度的导弹但之后的每一发高度都不能超过上一发。也就是说如果这套系统拦了一串导弹它们的下标按时间递增高度序列一定满足类似 h[1] h[2] h[3] ... 这样的关系。这个描述翻译成算法语言就是一套系统拦截的导弹序列是原序列中的一个不上升子序列。注意是“子序列”而不是“子串”意味着你可以跳过一些导弹不拦。很多新手一开始没转过这个弯总觉得系统必须从某发开始连续拦截实际上它们完全可以在中间放过几发直接去打后面更合适的目标。题目通常有两问第一问是“一套系统最多能拦截多少枚导弹”其实就是求原序列里最长的那个不上升子序列的长度第二问是“拦截所有导弹最少需要多少套系统”相当于把原序列拆成尽可能少的几个不上升子序列让每个导弹恰好分到一套系统里。这两问第一问是经典的最长不上升子序列LNDS第二问则是偏序集最小链覆盖问题答案等于最长严格上升子序列LIS长度。1.2 为什么“连续扫下降段”会挂我最开始的做法是维护一个当前系统的高度从第一发开始往后扫能拦就更新高度不能拦就换新系统。这个思路在简单数据上跑得很欢但遇到300 200 250 100这样的序列就崩了。按连续扫下降段的思路第一套系统从 300 开始拦下 300 和 200然后遇到 250 接不住了于是新开一套系统拦 250 和 100。这样算出来第一问的答案是 2也就是一套系统最多拦 2 发。但实际上一套系统完全可以拦 300、250、100 这三发中间跳过 200 不就行了所以答案是 3。问题出在哪关键是“实时贪心”只考虑了当前已经扫过的元素没有意识到跳过一些“碍事”的导弹反而可能让后续的链条更长。第一问本质是个全局最优问题必须用动态规划或者二分优化不能靠一次顺序扫描解决。至于第二问也绝不只是“数一数上升转折点再加一”这么简单后面我会用一个叫50 30 40的小样例说明。1.3 两个问题在算法上分别对应什么第一问对应最长不上升子序列这个好理解。第二问对应的是“把所有导弹划分成最少的下降链”这是一个非常漂亮的理论模型把每枚导弹看成元素定义一种偏序关系一套系统能拦截的导弹序列就是一条链最少系统数就是最少链覆盖数。这里先埋一个结论最少链覆盖数恰好等于最长反链长度。放到这道题里“反链”就是一个严格上升子序列因为严格上升的任意两发导弹都不可能由同一套系统拦截。所以第二问的答案直接等于原序列的最长严格上升子序列长度。这个结论来自 Dilworth 定理后面我会专门讲。2. 第一问最长不上升子序列怎么求2.1 最稳妥的 O(n²) 动态规划如果你只是想把题目先做对不管复杂度O(n²) 的动态规划是第一选择。状态定义很直接dp[i]表示以第 i 个导弹结尾的最长不上升子序列长度。因为不上升序列可以有中间被跳过的元素所以转移时要枚举所有在 i 之前的 j只要h[j] h[i]就可以把第 i 发接到以 j 结尾的序列后面。核心代码很短int n h.size(); vectorint dp(n, 1); int ans 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); } } ans max(ans, dp[i]); } cout ans \n;这里注意初始值必须全是 1因为单看任何一个导弹它自己都能构成一个长度为 1 的不上升子序列。复杂度 O(n²)在 n 只有几百几千的时候完全没问题。但洛谷 P1020 的数据范围已经被加强到了 n 可以达到十万级别O(n²) 稳超时所以必须上 O(n log n) 的优化。2.2 O(n log n) 优化d 数组里存的是什么优化的思路是用一个数组 d 维护“当前能构造出的最优子序列结尾”。很多人学过最长上升子序列LIS的二分优化下意识会认为这里也存“最小的末尾元素”但方向完全相反这是最容易绕晕的地方。先看 LIS严格上升的经典做法d 是递增数组d[i] 表示长度为 i1 的上升子序列中末尾元素的最小值。因为上升序列要求后面的元素大于末尾所以末尾越小后面能接的元素范围越大这就是为什么 LIS 里要维护“最小末尾”。但本题求的是不上升序列要求后面的元素小于等于末尾性质反过来了末尾越大后面能接的元素范围越大。所以 d 应该维护“末尾元素的最大值”并且 d 数组本身是递减的。d[i] 的含义是长度为 i1 的不上升子序列中末尾元素能取到的最大值。理解了这个关键点后面所有代码就顺了。遇到一个新导弹高度 x分两种情况如果x d.back()说明 x 能接在当前的“最长链条”后面直接追加否则 x 比当前最长链条的末尾还大不能接在最后。但 x 可以替换掉 d 中第一个小于 x 的位置让那个长度的不上升子序列拥有一个更大的末尾方便后续继续扩展。2.3 手写二分的代码与走查因为 d 是递减数组C 标准库的 lower_bound、upper_bound 默认处理递增数组直接套会出错。要么给比较函数要么手写二分。手写二分并不难关键是确定“找第一个小于 x 的位置”这个目标vectorint d; for (int x : h) { int l 0, r d.size(); while (l r) { int mid (l r) 1; if (d[mid] x) r mid; else l mid 1; } if (l (int)d.size()) d.push_back(x); else d[l] x; } cout d.size() \n;为什么d[mid] x时收缩右边界因为我们找的是第一个小于 x 的位置。d 是递减的如果中点已经小于 x说明答案在中点或者中点左边所以让 r mid如果中点是大于等于 x 的说明答案在中点右边所以让 l mid 1。最终 l 指向的如果不是末尾就替换如果是末尾说明所有 d 元素都大于等于 x那 x 本来就可以接到末尾。用300 200 250 100手动走一遍就很直观处理高度操作更新后 d300空数组直接加入[300]200小于等于尾部 300追加[300, 200]250大于尾部 200找第一个小于 250 的位置下标 1替换[300, 250]100小于等于尾部 250追加[300, 250, 100]最后 d 的长度是 3对应最优拦截方案300 250 100正确。2.4 另一种视角取负转成“最长不下降”再用 upper_bound手写二分虽然不复杂但每次都要想清楚“第一个小于”还是“第一个大于”写多了还是会烦。这里有个一劳永逸的转换技巧把每个高度取相反数。原问题要求h[i] h[j]取负之后变成-h[i] -h[j]等价于求取负后序列的最长不下降子序列。而不下降序列用 O(n log n) 求的时候d 是递增数组可以用标准库的 upper_bound找第一个大于 x 的位置替换。vectorint d; for (int v : h) { v -v; auto it upper_bound(d.begin(), d.end(), v); if (it d.end()) d.push_back(v); else *it v; } cout d.size() \n;这里为什么用upper_bound而不是lower_bound因为不下降序列允许相等遇到和 d 中元素相等的 x 时可以直接往后接不需要替换如果误用了 lower_bound等于把允许相等的情况当成严格上升处理结果会偏小。这个细节考试和面试里特别容易翻车。3. 第二问最少系统数的贪心思路3.1 贪心策略“够得着的里面选最矮的”第二问乍一看是模拟题但只要数据一大无脑模拟就废了。先看一个反例50 30 40。如果按“当前能接就接接不住就新开一套”的直觉先来 50第一套高度变成 50来 30 能接第一套高度变成 30来 40 发现第一套接不住30 40于是新开第二套最后用了 2 套。这个例子里面结果恰好是 2好像没问题。但你再想一种情况如果当前有两套系统第一套最后高度 30第二套最后高度 50来一个 40能接住它的是第二套而不是第一套。如果代码总是优先用“最近开的那套”去接就会错误地新开第三套。正确的贪心策略是维护一个数组 syssys[i] 表示第 i 套系统当前最后一发导弹的高度。每来一枚高度为 x 的导弹在所有sys[i] x的系统里选择sys[i]最小的那套来接并把它更新为 x如果所有系统都接不住也就是所有 sys[i] 都小于 x才新开一套。为什么选“最小的能接住的”因为高度更高的系统应当被保留下来去应对后面可能出现的更高导弹。这和生活中安排跑道的逻辑一样能降落的小飞机别占大飞机的跑道。3.2 用例子和表格演示 sys 数组的更新还是用300 200 250 100这个序列按上面的贪心走一遍。sys 数组在过程中始终保持有序这里是非降的所以可以用二分快速定位。导弹高度操作更新后 sys300没有系统能接新建[300]200系统 300 能接更新为 200[200]250系统 200 接不住新建 250[200, 250]100系统 200 能接选它更新为 100[100, 250]最终系统数是 2。这个结果和肉眼观察一致至少有两种方案第一套拦300 200 100第二套拦250或者第一套拦300 250 100第二套拦200。系统数都是 2。用 C 实现时sys 数组的非降性质可以直接配合 lower_boundvectorint sys; for (int x : h) { auto it lower_bound(sys.begin(), sys.end(), x); if (it sys.end()) sys.push_back(x); else *it x; } cout sys.size() \n;lower_bound找的是第一个 x的位置。这个位置就是“能接住 x 的所有系统里最后高度最小的那个”。如果没有这样的位置说明所有系统都接不住于是 push 新系统。替换后 sys 依然有序这个性质保证了下一轮还能继续用二分。3.3 为什么答案一定等于最长上升子序列长度第二问代码写完后很多人才会注意到这不就是 O(n log n) 求最长严格上升子序列长度的模板吗区别只是数组名字从 d 换成了 sys。这当然不是巧合。先给一个不太严谨但足够有用的直觉sys 数组在整个贪心过程中始终严格递增它实际上就是求 LIS 时维护的那个“最小末尾数组”。所以 sys 的最终长度就是原序列最长严格上升子序列的长度。如果还想再挖一层可以从两个方向证明下界至少需要 LIS 长度套系统取原序列的最长严格上升子序列那么这 L 个导弹里任意两个都因为后一个比前一个高不可能被同一套系统拦截。因为它们出现在同一套系统里的前提是“先拦截的高度必须不低于后拦截的高度”这里恰好违反了。所以至少需要 L 套系统。上界L 套系统一定够贪心算法维护的 sys 数组每一步都在表示“长度 i1 的严格上升子序列的最小末尾”这本身就是 O(n log n) 求 LIS 长度的算法。算法结束时的数组长度就是 L而贪心又确实构造出了一种不超过 L 套系统的分配方式所以 L 套足够。两个方向一夹结论就成立了。4. 用 Dilworth 定理把两个问题统一起来4.1 链与反链的直观理解第二问的结论如果只停留在“代码和 LIS 一样”会觉得有点神真正能让人通透的是 Dilworth 定理。它说的是在有限偏序集里最少链覆盖数等于最长反链长度。不用被“偏序集”这个词吓到。我们把导弹之间的关系定义成如果第 i 发导弹出现在第 j 发之前并且高度不低于它就认为这两发导弹“可比”可以在同一条链里。于是一套系统拦截的导弹序列就是一条链。最少需要几套系统就是最少能用几条链覆盖全部导弹。那反链是什么呢反链是任意两根导弹都不可比的集合。也就是说里面任意两根导弹都是“先出现的比后出现的低”放在一起看这就是一个严格上升子序列。所以最长反链长度就等于最长严格上升子序列长度。打个比方你要把一群人按身高从高到低排成尽量少的队伍允许跳人那么最少队伍数恰好等于这群人里能挑出的“严格越来越高”的最长小分队人数。听起来很违反直觉但定理保证这就是对的。4.2 最少系统数为什么就是最长反链长度有了这个框架第二问就不需要苦想贪心为什么对了。Dilworth 定理直接给出了答案最少系统数最少链覆盖数等于最长反链长度LIS 长度。第一问则是求最长链长度也就是最长不上升子序列长度。你会发现两个问题在偏序关系下是一对“对偶”问题一个求最长链一个求最少链覆盖。虽然第一问用 DP 或二分第二问用贪心或二分但底层是同一套结构。这也是为什么很多教材喜欢把这道《拦截导弹》放在“最长上升子序列”专题里讲。严格来说第一问是不上升子序列但把它和第二问的上升子序列放在一起对照着学反而比单学一个 LIS 更能理解边界条件。4.3 这个定理还能帮你秒答哪些变体理解了 Dilworth 定理后类似的题你基本一眼就能看出答案结构。比如把“一套系统只能拦截高度不高于上一发”改成“严格低于上一发”那么链就变成了严格下降子序列反链变成了不下降子序列最少系统数就是最长不下降子序列长度。改成“拦截高度不能低于上一发”那系统对应的是不下降子序列最少系统数就是最长严格下降子序列长度。其他场景比如把任务按截止时间排队一台机器只能处理截止时间单调变化的任务问最少需要几台机器本质上也是同一个模型。所以这道题真正的价值不是教你背代码而是让你学会把题目抽象成偏序关系然后用链覆盖定理直击答案。5. 完整 AC 代码与边界细节5.1 一份直接可提交的 C 代码把上面的思路整合成一份可以提交的完整代码第一问用取负转不下降的写法保持简洁第二问用 lower_bound#include bits/stdc.h using namespace std; int main() { vectorint h; int x; while (cin x) h.push_back(x); if (h.empty()) { cout 0 \n 0 \n; return 0; } // 第一问最长不上升子序列长度 // 取负后变成最长不下降子序列用 upper_bound vectorint d; for (int v : h) { v -v; auto it upper_bound(d.begin(), d.end(), v); if (it d.end()) d.push_back(v); else *it v; } cout d.size() \n; // 第二问最少系统数等价于最长严格上升子序列长度 // 用 lower_bound vectorint sys; for (int v : h) { auto it lower_bound(sys.begin(), sys.end(), v); if (it sys.end()) sys.push_back(v); else *it v; } cout sys.size() \n; return 0; }输入用while (cin x)可以处理任意行数的数据不用去数 n也不用担心每行末尾多换行。洛谷 P1020 的样例输入是一行但有些 OJ 喜欢把数据拆成多行这种写法最稳。5.2 最容易写错的四个细节第一个坑是等号。第一问不上升允许相等所以取负后要 upper_bound如果题目改成严格不上升取负后就是严格上升要用 lower_bound。第二问“能接住”默认也允许相等所以用 lower_bound如果改成严格低于才能接就用 upper_bound。等号一变二分函数就得跟着换。题目变体二分选择求的东西第一问不上升允许相等取负后 upper_bound最长不上升子序列长度第一问严格下降不允许相等取负后 lower_bound最长严格下降子序列长度第二问不高于即可接lower_bound最长严格上升子序列长度第二问必须严格低于才能接upper_bound最长不下降子序列长度第二个坑是 d 数组方向。手写二分求不上升子序列时d 是递减数组很多人会照抄 LIS 的递增二分写法导致结果全乱。如果不想背两种方向统一用取负转不下降就行。第三个坑是空输入。如果题目数据一开始就没有导弹直接输出两个 0。很多模板代码没写这个分支在部分测评数据下会越界或者输出错误。第四个坑是复杂度。n 小的时候 O(n²) DP 随便写但 n 到十万级别必须用 O(n log n)。我见过不少人第一问用 DP第二问用贪心二分混着交结果第一问超时这是很典型的失分点。两道题全部用二分版本复杂度才是一致的。5.3 Python 版本参考Python 的bisect模块对应 C 的 lower_bound 和 upper_bound写起来同样很短。注意读入用sys.stdin.read()能处理多行输入import sys import bisect h list(map(int, sys.stdin.read().split())) if not h: print(0) print(0) sys.exit() # 第一问取负后最长不下降子序列bisect_right 对应 upper_bound d [] for v in h: v -v pos bisect.bisect_right(d, v) if pos len(d): d.append(v) else: d[pos] v print(len(d)) # 第二问最长严格上升子序列bisect_left 对应 lower_bound sys_arr [] for v in h: pos bisect.bisect_left(sys_arr, v) if pos len(sys_arr): sys_arr.append(v) else: sys_arr[pos] v print(len(sys_arr))Python 的bisect_right就是 C 的upper_boundbisect_left就是lower_bound一一对应换语言也不容易写错。6. 从这题出发序列题里的贪心和 DP 还能怎么玩6.1 变了等号条件的几种常见变体很多题都是《拦截导弹》换了个壳。最常见的是把“不高于”改成“低于”那第一问就是最长严格下降子序列第二问答案变成最长不下降子序列长度。代码上基本只改一个函数但思路如果没跟上就会在等号边界上反复试错。还有一类变体是把“系统只能打一颗新的”改成“系统可以重置”但每次重置要付出代价问你最优收益这就在链覆盖的基础上引入了带权问题需要把二分的思路扩展成更复杂的规划模型。不过对新手来说先把等号规律背清楚已经能解决很大一部分衍生题了。6.2 接续型贪心 vs 边界扩张型贪心第二问的贪心属于“接续型贪心”每次来一个新元素在已有的系统里找最合适的位置续上去续不上去才新建。这类贪心通常配合有序数组加二分。但并不是所有贪心都是这个套路。比如“跳跃游戏2”那种求最少步数到达末尾的问题贪心维护的是当前这一步能跳到的最远右边界每次遍历完当前区间步数加一再扩大右边界。它不涉及“在已有选择里替换”而是不断扩张一个可达边界。两种贪心没有谁更高级但看到题目先判断“这一步是在选位置还是在扩展范围”能帮你少走很多弯路。6.3 我的一些个人心得做这道题最有价值的瞬间是我第一次手动算完300 200 250 100发现第二问的贪心跑完 sys 数组之后和 LIS 的维护数组长得一模一样。那一刻我才反应过来以前分开背的“LIS 二分模板”和“最少链覆盖贪心”其实是同一件事。如果你现在正卡在这类题上我的建议是不要只背代码。把 d 数组“存的是最大末尾还是不最大末尾”这个问题想清楚比多刷十道题都管用。我后来做很多序列题遇到不确定的情况都会先在草稿纸上写一个小样例手动推一遍 d 数组的变化再决定用 lower_bound 还是 upper_bound。这个方法看起来笨但真的能帮你省下大量的试错时间。