导弹拦截这个问题在算法圈里算是老面孔了。它表面上是一道模拟题实际考察的是最长上升子序列的变体和贪心策略的应用。很多初学者第一次做这道题都会被“第一问求最长不上升子序列第二问求最少系统数”这个组合搞晕——明明两个问题看起来差不多解法却完全不同。这篇文章我打算把这道题的每一个细节都拆开揉碎从暴力DP到二分优化从“为什么贪心是对的”到“等号到底怎么处理”一次性讲透。这道题适合正在学动态规划和贪心的读者也适合准备机试、笔试但总在LIS变体上卡壳的人。看完之后你不仅能AC这道经典题还能把“最长上升子序列”这个知识点的底层逻辑真正吃透。1. 题目理解与整体思路拆解1.1 题意到底在说什么先还原一下题目的原始场景某套防御系统发射的拦截导弹每一发炮弹都有一个最大飞行高度而且这套系统有个硬性规定——炮弹拦截的高度必须严格递减也就是说第一发能打到10000米第二发最多只能打9999米不能反弹回去打更高的目标。现在给出一串来袭导弹的高度序列比如389 207 155 300 299 170 158 65问两个问题一套系统最多能拦截多少枚导弹要拦截所有导弹最少需要几套系统注意这两问的微妙之处。第一问是“在保证拦截顺序合法的情况下最多能拦截几枚”这本质上是在一个序列里找一段尽可能长的、单调不上升的子序列。第二问则变成了“如何用最少的递减序列把整个序列覆盖掉”这是一个划分问题不是子序列问题。很多教程会把这两问都归到LIS上但第二问其实更贴近贪心的“最小链覆盖”思想。把这两个问题放在一道题里就是为了考察你能否区分“最长子序列”和“最少覆盖序列”这两个概念。如果混为一谈第二问十有八九会写成“求最长上升子序列长度”然后直接输出答案恰好在某些样例上也能过但本质上是错的。1.2 第一问的暴力DP为什么是O(n²)第一问是经典的最长不上升子序列。定义dp[i]表示“以第i枚导弹结尾的最长不上升子序列长度”。为什么一定要强调“以第i个元素结尾”因为子序列的连续性不是按位置来的而是按逻辑关系来的。转移的思路是对于每个i往前找所有高度不小于a[i]的j只要a[j] a[i]就意味着第i枚导弹可以接在第j枚导弹后面形成合法的不上升关系。所以dp[i] max(dp[j] 1) 其中 j i 且 a[j] a[i]初始状态是dp[i] 1表示单独一枚导弹也能构成一个长度为1的序列。这个做法的时间复杂度是 O(n²)因为每个i都要扫描前面所有的j。当 n 在1000以内时完全没问题但如果 n 到了100000O(n²)就暴毙了。这也引出了后面的二分优化方案后面我会专门讲。1.3 第二问的贪心直觉第二问如果按直觉来想最简单的策略就是“能拦就拦”。每次来一枚新导弹先在现有的拦截系统里找一套“高度够高、但又不会浪费”的系统来拦它。这里的“不会浪费”四个字是关键。比如当前两套系统的最高可拦截高度分别是300和200现在来了一枚250的导弹。用300的那套能拦用200的那套拦不了。虽然两套都能用300那套来拦但更好的策略是保留300那套因为它以后还能拦更高的导弹。如果现在把300那套用了之后来一枚280的导弹就只能再开新系统白白浪费。所以第二问贪心的核心是每次选择“当前可拦截高度大于等于目标高度且是所有可用系统中可拦截高度最小”的那一套。如果所有系统都拦不了才新建一套系统新系统的高度上限就是这枚导弹的高度。这个策略可以保证系统数量最少后面我会结合“决策单调性”来解释它为什么是对的而不是靠感觉。2. 第一问深入最长不上升子序列的DP推导2.1 状态转移的完整推演我们拿题目自带的示例序列来手跑一遍a [389, 207, 155, 300, 299, 170, 158, 65]初始化全部dp[i] 1。i1a[1]389前面没有元素dp[1]1i2a[2]207往前找389 207所以dp[2] dp[1]1 2i3a[3]155往前找389 155207 155分别算得2和3取最大dp[3] 3i4a[4]300往前找389 300得到2207 300不能接155 300不能接。所以dp[4] 2i5a[5]299往前找389 299得到2207 299不行155 299不行300 299得到 dp[4]13所以dp[5] 3i6a[6]170往前找389、207、300、299都 170其中dp[5]14dp[2]13dp[4]13最大的是4所以dp[6] 4i7a[7]158往前找dp[6]15最大所以dp[7] 5i8a[8]65往前找dp[7]16最大所以dp[8] 6最终答案不是dp[n]自动等于6吗恰好在这个例子里是。但如果导弹高度是递增的比如1 2 3 4 5算出来的dp[1]1, dp[2]1, ..., dp[5]1最大答案应该是1但dp[n]也是1碰巧一致。如果序列是5 1 2 3 4答案应该是25 4或者5 3之类但dp[4]是以4结尾的序列长度算出来是25 4之间的dp值是2还是碰巧。真正能暴露问题的是1 3 2这样的序列答案应该是2dp[2]1以3结尾的最长不上升是1dp[3]2以2结尾可以接3但如果你只输出dp[n]会得到2恰好对再来一个3 1 2答案应该是23 1或者3 2dp[2]2dp[3]2还是对。这里要特别提醒很多题解会直接输出dp[n]在大多数测试点能过但逻辑上不严谨。正确答案应该取dp数组的最大值而不是dp[n]。因为最长不上升子序列不一定结束在最后一个元素上。比如序列5 3 4 2 1最长的是5 3 2 1长度4结束在最后一个元素但如果序列是5 1 4 3 2最长可以是5 4 3 2结束在最后一个也碰巧。真正反例是2 1 3最长不上升是2 1或3最长长度2而dp[3]是以3结尾的序列长度只有1。如果只看dp[n]就错了。2.2 相等高度的处理不上升 vs 严格下降题目要求“每一发炮弹的高度不得高于前一发的高度”也就是允许相等。这意味着转移条件是a[j] a[i]而不是a[j] a[i]。这里是最容易踩坑的地方。如果写成a[j] a[i]你求的就是“最长严格递减子序列”而题目要求的是“最长不上升子序列”两者在高度重复出现时结果完全不同。举例5 5 5 5最长不上升子序列是4因为可以连续拦截4枚高度都为5的导弹。但如果写成严格递减那答案就变成了1瞬间WA。所以记住这个口诀题目说“不高于”就是题目说“低于”才是。同样思路也适用于最长上升子序列和最长严格上升子序列的区别。2.3 代码实现与细节第一问的O(n²)实现非常短#include bits/stdc.h using namespace std; int main() { vectorint a; int x; while (cin x) a.push_back(x); int n a.size(); vectorint dp(n, 1); int ans 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } cout ans endl; return 0; }几个细节提一下输入是不定长的用while (cin x)或者getline切割都行。初始化dp全为1这个不能省。任何单个元素自己就是一个合法的子序列。答案是ans全局最大值不是dp[n-1]。这个代码在 n 1000 的范围内性能足够笔试机试基本都能过。但如果数据范围到了 10^5 甚至 10^6就必须换二分优化了。3. 第二问深入贪心模拟拦截系统3.1 贪心策略的完整描述第二问常见的解法有两种一种是“每来一枚导弹在现有系统里找能拦住它的、且当前高度上限最小的系统”另一种是“用数组模拟每个系统的当前高度每次更新”。我把第一种策略写成通俗的语言维护一个数组syssys[k]表示第 k 套系统当前能拦截的最高高度。每来一枚高度为 h 的导弹遍历所有现有系统找出满足sys[k] h的系统里sys[k]最小的那个。如果找到了就把这个系统的sys[k]更新为h因为拦截了这枚导弹后这套系统的能力上限就降到了 h。如果没找到说明所有系统都拦不了这枚导弹就新开一套系统把 h 加入sys数组。最后sys的长度就是所需系统数。为什么选择“能力上限最小且能拦住”的系统因为我们要“节省火力”。用一个能拦300米高度的系统去拦100米的导弹虽然能拦但浪费了200米的余量。万一后面来一枚280米的导弹本来300米系统可以拦结果被100米的导弹消耗掉了就只能新建系统。3.2 手工推演示例还是拿示例序列跑一遍389 207 155 300 299 170 158 65来389sys为空新建sys [389]来207389 207更新389为207sys [207]来155207 155更新207为155sys [155]来300155 300拦不了新建sys [155, 300]来299155 299但300 299且300是所有可用系统里高度最小的另一个155不够格更新300为299sys [155, 299]来170155 170但299 170更新299为170sys [155, 170]来158155 158但170 158更新170为158sys [155, 158]来65155 65更新155为65sys [65, 158]最终需要2套系统。第一套拦截了389、207、155、65第二套拦截了300、299、170、158。这个结果很符合直觉高度整体呈下降趋势时一套系统就能覆盖大部分但300这个突然拔高的数值打断了一次连续性所以需要第二套系统接住那一段相对较高的导弹。3.3 贪心正确性的证明思路第二问的贪心策略看起来显然但要严格证明并不简单。这里提供一个比较直观的证明思路不涉及复杂的数学工具。假设我们当前有一组系统编号1到m。每来一枚导弹h按照策略我们找到了第k号系统来拦截它k满足是“所有能拦截系统里高度最小的”。现在考虑任何其他合法策略在这次决策时选择了一个不同的系统 k 来拦截h。因为k是我们选的最小值所以sys[k] sys[k]。更新后k系统变为hk系统变为h其他系统不变。比较两种决策后的状态我们的策略让第k号系统的高度变成了h而其他策略让第k号系统变成了h。我们的系统中被“消耗”的是一个原本高度更小或相等的系统也就是说我们把高度更大的那个系统保留了下来。保留更高能力的系统意味着以后面对更高的导弹时我们有更多选择余地。所以我们的决策不会比任何其他决策更差。不断重复这个归纳过程贪心策略的最终系统数一定不大于任何其他策略的系统数于是它就是最优解。这个证明的核心就是“保留高能力资产”。在代码里这个策略对应的是每次找一个 h的最小值也就是 lower_bound 的变体。3.4 第二问代码实现#include bits/stdc.h using namespace std; int main() { vectorint a; int x; while (cin x) a.push_back(x); vectorint sys; for (int h : a) { bool ok false; int best -1; int bestIdx -1; for (int i 0; i (int)sys.size(); i) { if (sys[i] h) { if (bestIdx -1 || sys[i] best) { best sys[i]; bestIdx i; } } } if (bestIdx ! -1) { sys[bestIdx] h; } else { sys.push_back(h); } } cout sys.size() endl; return 0; }这里有个容易犯的错误很多初学者会写成“找到第一个大于等于h的系统就更新”但如果你找到的是高度300的系统而不是高度155的系统假设两者都能拦当前导弹就可能造成浪费。必须强调“最小可用”三个字。4. 从O(n²)到O(n log n)二分优化全解析4.1 为什么需要优化当数据范围变大n 100000 甚至更大时O(n²)的DP会超时。第一问和第二问都需要更高效的解法。第一问的经典优化是“贪心 二分”也就是维护一个数组dd[i]表示“长度为 i 的不上升子序列的最后一个元素的最大值”。听起来有点绕我们拆开说。核心思想是在构建子序列时我们希望“末位元素尽可能大”这样后面才有更多元素能接上去。比如当前已经有不上升子序列长度为2可能存在多个长度为2的不上升子序列它们的末位元素分别是30和50。显然50更好因为后面要接一个比50更小的元素比接在30后面更容易。所以我们可以维护一个数组dd[len]表示“所有长度为 len 的不上升子序列中末位元素的最大值”。然后遍历导弹高度时要么扩展新的长度要么更新已有长度的末位值。4.2 第一问的二分优化细节处理不上升子序列时d数组是单调不递增的还是单调递减的我们来分析。假设d[1] d[2] d[3]这个性质必须成立。因为长度为2的不上升子序列的末位元素必然不大于长度为1的不上升子序列的末位元素否则长度为2的子序列就能和长度为1的子序列组合成更长的序列。这个性质可以通过归纳法严格证明。遍历每个高度h时我们要找的是“d中第一个小于 h 的位置”。为什么是“小于”而不是“小于等于”因为不上升子序列允许相等。假设d [50, 40, 30]现在新来一个h 40它应该接在哪个长度后面长度为1的子序列末位是5040 50可以接在后面形成[50, 40]长度2。但d[2]已经是40新形成的也是40没变化。长度为2的子序列末位是4040 40可以接形成长度3。所以新来的40应该更新d[3]为40。这里d[3]原本是30现在可以提升为40。所以我们要找的是“d中第一个小于h的位置”如果d中所有元素都不小于h说明h可以接在最长子序列后面扩展出一个新长度。用 C 的upper_bound配合自定义比较器来实现或者手写二分。这里的关键是明白upper_bound找的是“第一个大于h”的位置而我们需要“第一个小于h”的位置正好相反所以要自定义比较规则。一个更稳妥的写法是手写二分vectorint d; d.push_back(a[0]); for (int i 1; i n; i) { int h a[i]; if (h d.back()) { d.push_back(h); } else { // 在d中找第一个小于h的位置替换为h int l 0, r d.size() - 1; while (l r) { int mid (l r) / 2; if (d[mid] h) r mid; else l mid 1; } d[l] h; } } cout d.size() endl;这里的d.size()就是最长不上升子序列长度。4.3 第二问的二分优化第二问的贪心策略里我们需要在系统数组中找“第一个大于等于h的元素”然后把它替换为h。如果没找到就push_back。系统数组sys是天然有序的吗按贪心策略更新后它始终保持递增吗我们来看每次把sys[k]更新为 h sys[k]数组还是有序的。每次新开系统加入 h而h一定大于当前所有系统的值因为所有系统都拦不了它所以h会成为数组最大元素加入后依然有序。既然有序就可以用二分查找定位替换位置。C 里直接用lower_bound找第一个 h的元素即可vectorint sys; for (int h : a) { auto it lower_bound(sys.begin(), sys.end(), h); if (it ! sys.end()) { *it h; } else { sys.push_back(h); } } cout sys.size() endl;这段代码极其简洁。lower_bound返回第一个不小于h的位置直接替换完美对应贪心的“最小可用系统”。4.4 Dilworth定理两问之间的桥梁第二问还有一个很著名的结论最少不上升子序列划分数等于最长上升子序列长度。这就是Dilworth定理在序列上的特例。偏序关系定义为“i j 且 a[i] a[j]”那么最长链的长度就是不上升子序列最大长度最小链覆盖数就是最长反链的长度而最长反链就是最长上升子序列。也就是说第二问可以直接用求LIS的方法做求一遍最长上升子序列注意是严格上升不是非降输出长度即可。这个发现让人非常爽因为两问都可以用LIS的变体统一解决。代码上只需要把第一问的“不上升”改成“上升”再跑一遍即可。但要注意“上升”和“非降”的区别第二问对应的是最长“严格上升”子序列不是非降子序列。为什么直观的解释是如果两个导弹高度相同比如5 5一套系统可以拦下两枚意味着“高度相等”不算上升关系。那么关键的结论是用最少的不上升序列覆盖一个序列需要的数量等于最长严格上升子序列的长度。如果误写成非降子序列5 5就会被算成长度为2的递增关系答案变成2而实际上1套系统就够。所以再次强调第一问是不上升第二问对应的是上升两者在相等时刚好互补。写代码时一定要小心。5. 常见问题与调试经验5.1 输出dp[n]导致的隐蔽错误这个问题我前面提过但值得单独拿出来再说一遍。很多AC代码确实只是输出dp[n]因为大部分测试数据里最长不上升子序列恰好结束在最后一个元素。但如果你用1 3 2这种用例测试dp[2]以3结尾是1dp[3]以2结尾是2如果输出dp[n]恰好是2还是对。真正的反例需要让最长序列不结束在末尾。比如5 1 4 3 2最长不上升子序列是5 4 3 2结束在末尾还是碰巧。那5 4 1 3 2 6呢最长不上升是5 4 3 2结束位置是倒数第二dp[n]是1以6结尾如果用dp[n]就会WA。所以写DP时养成分开维护答案的习惯别偷懒直接用dp[n]。5.2 等号方向混淆这是另一大坑。第一问遇到相等高度时比如3 3允许连续拦截所以答案是2。如果写成a[j] a[i]打印出来的答案是1瞬间WA。第二问的Dilworth定理对应最长严格上升子序列如果第二问误写成非降子序列遇到3 3这种用例会输出2而正确答案是1一套系统能拦下两枚高度相同的导弹。怎么记忆可以用物理直觉一套系统拦完一枚导弹后上限降到这枚导弹的高度。如果下一枚导弹高度相同它不高于当前上限所以能拦。因此不上升序列允许相等。对应地第二问需要的是“打破不上升覆盖的最少数量”这个数量只有在严格上升时才增加所以是严格上升子序列长度。5.3 二分边界写错的排查手写二分的题解里最常见的bug是边界条件。比如第一问的二分要小心l和r的初始值以及mid的取值方向。一个建议不要死记模板把二分退化成“在有序数组中找到第一个满足条件的位置”然后用左闭右开区间写int l 0, r d.size(); // 左闭右开 while (l r) { int mid (l r) / 2; if (d[mid] h) r mid; else l mid 1; } d[l] h; // 或者 d.insert(d.begin()l, h)这个写法更不容易出错。注意当l等于d.size()时表示没有找到需要push_back而不是直接赋值。5.4 关于二分优化的常见疑问有读者会问第一问的d数组能求出具体的子序列吗很遗憾不能直接用最终d数组还原出最长的那个子序列因为d只记录了每个长度的最佳末位值过程中可能丢失了中间元素的信息。要还原具体子序列需要额外维护一个pos数组记录每个元素在DP过程中被安排到了哪个长度位置然后从后往前回溯。这个复杂度虽然还是O(n log n)但实现复杂度高不少。笔试面试一般只要求输出长度所以还原子序列的需求不常见。但如果想深入理解建议自己推一遍。5.5 数据读取的问题题目输入是“第一行是一枚导弹的高度第二行是下一枚导弹的高度以此类推以文件结束符结束”。也就是说可能是一行一个数也可能是空格分隔的一行数。用while (cin x)是最稳妥的写法不管什么格式都能正确读完。有些初学者会用getline读整行然后 split遇到多行的输入格式就会出错。直接用cin流读取是最省心的方案。6. 题型扩展与进阶思考6.1 拦截导弹变体这道题有很多变体万变不离其宗把“不上升”改成“严格下降”第一问转移条件变成第二问对应最长非降子序列长度。把“导弹高度”改成“导弹速度和高度双属性”需要先按速度排序再对高度做LIS这就是经典的二维偏序问题。如果允许“同时发射多枚拦截弹”本质还是最少系统数问题但每套系统的能力不再是固定的而是可以动态调整这就要用上贪心的“最小可用系统”思想。6.2 从这题延伸出去的LIS全家桶最长上升子序列问题本身变种极多最长不降子序列转移条件a[j] a[i]第二问对应最长严格递减子序列长度。最长递减子序列把数组翻转后求最长递增即可。带权LIS每个元素有值和权重求权重和最大的递增子序列这个需要树状数组优化。循环数组LIS数组可以循环移位求所有可能起点下的LIS最大值这个通常需要把数组复制一倍再处理。理解了拦截导弹这道题等于把LIS系列的核心套路都过了一遍。6.3 贪心与DP的分工最后聊聊一个更宏观的问题什么时候用贪心什么时候用DP这道题提供了一个很好的对比样本。第一问求的是“全局最优子序列长度”这是一个典型的DP问题因为状态之间存在依赖关系需要记录从任意位置开始到当前位置的最优值。第二问求的是“最少系统数”这个看上去也像DP但贪心恰好能够解决因为每次决策只需要考虑“当前哪套系统最合适”而不用考虑未来因为“保留更高上限系统”的策略具有局部最优性。判断的标准是如果一个决策的最优性可以从当前状态直接推导出来不依赖未来信息那贪心往往可行如果当前决策会影响未来很多步的选择那可能就是DP的范畴。LIS问题里“贪心二分”的优化本质上是用贪心维护了DP的更新这是更高级的用法值得反复琢磨。6.4 机试实战中的时间分配如果你正在准备机试我的建议是看到这类经典题先静下来把两问的含义理清楚别急着写代码。用样例手推两遍确认第一问的DP转移和第二问的贪心策略然后再动手。机试中时间复杂度往往比空间复杂度更容易卡人。n在1000以内时O(n²)完全够用n到1e5就必须用O(n log n)的解法。如果对二分不熟建议先把暴力写出来保证能过一部分测试点再优化。还有一种常见情况是题目没有告诉你n的范围这个时候“能优化就优化”是最稳妥的策略。LIS的二分优化代码量很少背下来绝对不亏。写在最后这道拦截导弹我前前后后教过很多人也见过无数种写法。有时候同一个代码换一批测试数据某些错误的写法就暴露了。所以每次我都强调不要背题解一定要亲手推一遍状态转移亲手试几个反例。我个人觉得这道题最宝贵的地方在于它把“DP求最优子序列”和“贪心求最小覆盖”这两个看似不同、实则互补的思想放在了同一道题里。想清楚“为什么第一问不能用贪心直接求”“为什么第二问不用DP也能做”比AC这道题本身更重要。如果你现在看完这篇文章能自己推导出第二问的lower_bound更新过程并且能解释清楚为什么Dilworth定理在这里成立那说明你是真的吃透了。以后再遇到LIS的变种题心里会踏实很多。