第一次在题目列表里看到[SSL1082] 拦截导弹我还以为又是一道入门 DP。后来仔细一读才发现它把两个经典问题绑在一起先让你算最长不上升子序列再让你算最少需要的拦截系统数量后者在不少资料里被标成最小路径覆盖。这两个标签放在同一道题里看起来很像其实思维方式完全不同。如果你已经会第一问却被第二问绕进去那这篇就是为你准备的。题面的核心是一枚枚导弹按顺序飞来每枚有高度 h。一套拦截系统发射后后续每发炮弹的高度不能高于前一发也就是系统拦截的导弹高度序列必须不上升。第一问问给定整个序列最多能拦下多少枚允许跳着拦但必须按来的顺序第二问问若要全部拦完最少需要多少套系统。第一问求的是“从一个序列中选一个最长子序列”第二问求的是“对整个序列做最优划分”前者是长度后者是系统数量两者的答案计算方式并不一样。很多人把这题当成两道题分别套模板结果第一问用最长不上升第二问莫名奇妙也想用不上升最后全错。实际上第二问的答案是最长严格上升子序列长度。不理解背后原因的话基本只能靠背结论换一道题就不会了。下面我从题意、理论、代码、排错四个角度把这道题彻底拆开。1. 先看懂这道题两个问题两种算法思想1.1 题面在说什么先明确输入输出。通常第一行是导弹数量 n第二行是 n 个高度值。你需要输出两行第一行是最长不上升子序列长度第二行是最少系统数。也就是说题目要你同时解决两个独立的优化问题但它们建立在同一个序列上所以解题时很容易混在一起。第一问可以理解成在导弹序列中选一个子序列允许跳着选但保持原始顺序选出的高度序列要满足“后一个不超过前一个”也就是 h[i] h[j]i 在 j 前面。问这个子序列最长能有多长。这是经典的最长不上升子序列问题一般写成 LNDSLongest Non-Increasing Subsequence。第二问理解起来更接近实际一套系统一旦开始工作它能拦截的导弹高度必须不上升但多套系统可以同时存在。如果第一套拦了 389后续来一枚 300它可以继续拦但再来一枚 400这套系统就接不住了必须换一套系统。问最少需要几套系统把全部导弹都拦下来。这个问题从偏序和链覆盖角度看有一个非常漂亮的结论答案等于最长严格上升子序列长度。适合读这篇内容的人是已经接触过最长上升子序列LIS模板但不太清楚不上升变体怎么处理的选手。如果你连朴素 DP 都没写过建议先补一下 LIS 基础再回来看优化和 Dilworth 定理部分。1.2 两个问题的数学关系链与反链为了解释第二问得引入一点偏序集概念但不复杂。把每枚导弹看成一个元素定义一个可比关系导弹 i 可以排在导弹 j 前面当且仅当 i 在原序列中位于 j 之前且 h[i] h[j]。如果两个导弹满足这个关系它们就能被同一套系统依次拦下。这个关系满足传递性所以它是一个偏序关系不是单纯的前后顺序。在这个偏序集里一串满足“每相邻两个都可比”的元素叫链一条链正好对应一套系统实际发射的序列。比如 389 - 300 - 299 - 170就是一条链。而一个集合里如果任意两个元素都不可比叫反链放在导弹问题里任意两个都不可比意味着后出现的导弹高度严格大于前一枚也就是一个严格上升子序列。于是第一问求的是最长链长度第二问求的是最少链覆盖数。Dilworth 定理告诉我们有限偏序集的最小链覆盖大小等于最大反链大小。所以第二问等于求最长严格上升子序列长度。看到这里第二问为什么不是最长不上升子序列已经很清楚覆盖全部元素时无法共用一套系统的那些导弹才决定系统数量的下限而那些导弹集合正是严格上升的。1.3 等号怎么处理是第一个坑题目写的是“不高于”也就是允许相等。两枚高度相同的导弹完全可以由同一套系统连续拦截第一发高度 100第二发高度 100100 100合法。因此在第一问里不上升子序列允许相邻相等在第二问的反链里严格上升才意味着不能共用所以等号不能算。二分模板里这个差别直接体现在用 lower_bound 还是 upper_bound。第一问如果按取负求不下降用 upper_bound第二问求严格上升的 LIS用 lower_bound。很多同学背模板时搞混就是因为没搞清楚允许相等时边界应该往哪边偏移。如果你在做题时发现样例能过、随机数据偶尔出错优先检查等号处理。这个坑我踩过不止一次后来我养成了一个习惯每写完一个 LIS 变体先拿一组全是相同高度的数据测一遍比如 [5,5,5,5]第一问应该输出 4第二问应该输出 1。如果输出不对说明二分边界写反了。2. 第一问最长不上升子序列的朴素 DP 与二分优化2.1 朴素动态规划先把转移写对先不急着优化把状态定义清楚。设 dp[i] 表示以第 i 个导弹结尾的最长不上升子序列长度。对于第 i 个导弹它可以从前面任意一个高度不低于 h[i] 的导弹接过来所以转移是dp[i] 1 max(dp[j])其中 j i 且 h[j] h[i]。如果前面没有可以接的dp[i] 就是 1。答案取所有 dp[i] 的最大值。这个 O(n^2) 做法在 n 只有几百时完全没问题但拦截导弹这题 n 稍微一大就超时。我建议在本地对拍时保留这个朴素 DP它是验证二分优化是否正确的最好参照物。二分写起来容易自我感觉良好但你拿朴素 DP 的结果一对比写错的地方马上现形。举个例子序列 389 207 155 300 299 170 158 65手算前几个dp[0] 1dp[1] 2389 207dp[2] 3389 155207 155dp[3] 2只有 389 300207 和 155 都小于 300。继续算下去最大 dp 值是 6。这个 6 对应 389、300、299、170、158、65 这条链。2.2 二分优化取负变成最长不下降最长不上升子序列的二分优化直接按原序列写也不是不行但细节比较多。我自己习惯先取负b[i] -h[i]。原序列 h 中 h[i] h[j] 等价于 b[i] b[j]也就是说原序列的最长不上升子序列变成了新序列 b 的最长不下降子序列。求最长不下降子序列的维护方法和标准 LIS 几乎一样。维护一个单调不降的数组 dd 的长度表示当前最长长度。每遇到一个 x在 d 中用 upper_bound 找第一个大于 x 的位置如果没有x 可以接在所有现有序列后面直接 push_back如果有把这个位置的值替换成 x。最后 d.size() 就是答案。为什么用 upper_bound 而不是 lower_bound因为不下降允许相等。如果 d 里已经存在等于 x 的末尾x 可以接在这个末尾后面形成更长的序列所以应当跳过等于 x 的元素去找第一个大于 x 的。标准严格上升 LIS 才用 lower_bound遇到相等的只能替换不能追加。这个区别是所有变体的核心。2.3 手动演算一遍看 d 数组怎么变化拿经典样例来说389 207 155 300 299 170 158 65。取反后是 -389 -207 -155 -300 -299 -170 -158 -65。逐个处理d 的变化如下。步骤原高度取反 b操作后 d当前长度1389-389[-389]12207-207[-389, -207]23155-155[-389, -207, -155]34300-300[-389, -300, -155]35299-299[-389, -300, -299]36170-170[-389, -300, -299, -170]47158-158[-389, -300, -299, -170, -158]5865-65[-389, -300, -299, -170, -158, -65]6注意第 4 步-300 到来时d 是 [-389, -207, -155]第一个大于 -300 的是 -207不是 -389。负数比较在这里非常容易看错我第一次演算就栽了。代码里不需要人眼看但手推时一定要想清楚。最终长度 6和预期一致。3. 第二问最少拦截系统数从贪心到 Dilworth 定理3.1 模拟系统拦截过程能者上择优录取如果不用 LIS 结论第二问最直观的做法是模拟贪心。维护一个 multiset里面存的是每套系统当前最后拦截的那枚导弹高度。遇到新导弹 x先在 multiset 里找所有高度 x 的系统如果找不到说明所有系统都接不住 x必须新开一套。如果找得到选其中“高度最低的那套”去拦截。为什么选高度最低而不是任意一套因为要把更高的系统留给后面更高的导弹。举个例子现在系统里一个末尾是 300一个末尾是 200新导弹高度 180两个都能接。如果用 300 那套接200 那套留空后面来一枚 250只能用新系统但如果用 200 那套接后面 250 可以让 300 那套接就不用新增。这个小决策就是贪心最优性的来源。实现上用 multiset 的 lower_bound(x) 可以直接找到第一个 x 的系统。找到就删掉旧高度插入 x找不到就插入 x 表示新系统。最后的 multiset.size() 就是答案。这个做法的时间复杂度也是 O(n log n)非常稳健。3.2 为什么最少系统数恰好等于最长严格上升子序列长度贪心模拟能得到答案但我们还可以从理论上解释。回到 1.2 节的链与反链一套系统是一条链最少系统数是最小链覆盖数。Dilworth 定理说这个数等于最大反链大小。反链在这里就是任意两个导弹都“不能由同一套系统连续拦截”也就是后面导弹高度严格大于前面导弹正好是最长严格上升子序列。这就是为什么第二问的代码和第一问只差一个二分边界第一问求最长不上升第二问求最长严格上升。很多解法的最终代码都只写两个二分函数第一个对取反序列求不下降第二个对原序列求严格 LIS。两个函数都返回 d.size()加起来就是一题的两个答案。有一个容易混淆的点既然第二问等价于最长严格上升子序列那它属于最大反链问题。所以你在网上看到的最小路径覆盖、Dilworth 定理、贪心导弹系统指的都是同一件事只是叙述角度不同。做题时不需要纠结名称抓住最本质的偏序关系就行。3.3 标题里的“最小路径覆盖”到底指什么把每枚导弹变成一个点如果 i 在 j 之前且 h[i] h[j]就画一条从 i 到 j 的有向边。这样一套系统拦截的导弹序列就是一条路径。题目要求用尽量少的路径覆盖所有导弹点这就是有向无环图上的最小路径覆盖问题。对一般 DAG最小路径覆盖数 顶点数 - 最大匹配数需要拆点后跑二分图匹配。但这道题的图不是一个普通 DAG它由偏序关系生成有非常强的传递性所以可以绕过匹配直接用 Dilworth 定理得到更简单的结论。如果题目改成一堆随机点之间的任意依赖关系贪心就不一定能用了那时候才需要真正的二分图匹配。所以标题里写最小路径覆盖更多是提醒你这是一类偏序集划分问题。面试或比赛中遇到“最少链覆盖”“最少系统数”“最少队伍数”这类说法第一反应不是暴力枚举而是想 Dilworth 定理和最长反链。4. 完整代码与边界测试可以直接抄走的实现4.1 C17 实现双问一次跑完下面这份代码是我自己常用的版本输入第一行为导弹数量 n第二行为 n 个高度。两个问题分别用一个函数全部用二分O(n log n)。#include bits/stdc.h using namespace std; int longestNonIncreasing(const vectorint a) { vectorint d; for (int x : a) { x -x; // 取负求最长不下降 auto it upper_bound(d.begin(), d.end(), x); if (it d.end()) d.push_back(x); else *it x; } return (int)d.size(); } int longestStrictIncreasing(const vectorint a) { vectorint d; for (int x : a) { auto it lower_bound(d.begin(), d.end(), x); if (it d.end()) d.push_back(x); else *it x; } return (int)d.size(); } int main() { int n; while (cin n) { vectorint a(n); for (int i 0; i n; i) cin a[i]; cout longestNonIncreasing(a) \n; cout longestStrictIncreasing(a) \n; } return 0; }4.2 代码解读两个二分函数为什么这样写longestNonIncreasing 里取负后x 变成 -h。upper_bound 找的是 d 中第一个大于 x 的位置替换它。这对应“不下降子序列中允许相等”的语义。d 数组不是实际子序列只是维护一个能支撑长度的末尾值集合所以看 d 的中间过程不要试图去原序列里找到完全对应的串。longestStrictIncreasing 就是标准 LIS。lower_bound 找到第一个大于等于 x 的位置替换或者追加。因为严格上升要求后面的数严格更大遇到相等不能接在后面只能替换掉已有的相等值。两个函数看起来很像但一个 upper_bound一个 lower_bound差之毫厘谬以千里。main 里用 while (cin n) 是为了兼容多组数据输入。有的题面是直到文件结束有的只给一组写成 while 循环都不会错。如果题目保证只有一组也可以去掉 while但保留的话即使输入后面还有第二组样例程序也能继续处理不会卡住。4.3 边界用例与结果验证我把常用测试数据整理成一张表跑代码之前先对一遍。输入第一问第二问解释空00没有导弹双方无意义511单个导弹一套系统5 5 5 541等高全可拦只用一套1 2 3 4 515上升序列每个都要新系统5 4 3 2 151下降序列一套到底389 207 155 300 299 170 158 6562经典样例空输入如果按 while(cinn) 读不到 n 就直接退出所以不会输出 0 0。这里的边界表主要是提醒你用手算验证逻辑。实测每一组都符合预期尤其是 5 5 5 5能同时验证 upper_bound 和 lower_bound 的等号处理。5. 实战中的常见问题与排查经验5.1 第一问二分用错 upper_bound / lower_bound最经典的错误就是把第一问也写成 lower_bound。试想取负后如果 x 等于 d 里某个值用 lower_bound 会找到第一个等于 x 的位置并替换不下降序列本来可以把 x 接到这个值后面形成更长序列结果被当成严格递增处理长度会偏小。拿 5 5 5 5 一测立刻现形。我现在每次写完二分都会找三种数据各测一组全部相等、全部递增、全部递减。全部相等验证等号全部递增验证系统数全部递减验证不上升长度。三个都过了基本不会再有边界问题。不要嫌麻烦这个习惯能省下大量 debug 时间。5.2 第二问把相等高度误判成需要新系统第二问若用贪心模拟multiset 的 lower_bound 应该找第一个 x 的系统而不是第一个 x。如果写成 那高度相等的导弹会被认为没有系统能接硬生生多开一套。代码层面就是 lower_bound 和 upper_bound 的区别。从 LIS 角度看第二问要求的是最长严格上升子序列长度。如果你不小心把第二问也写成了不下降5 5 5 5 会输出 4而不是正确答案 1。这类题样例通常给得不全一定要靠边界用例自己兜底。5.3 输入格式不统一怎么办这道题在不同题库里的输入格式经常不一致。有的先给 n 再给数组有的直接把所有导弹高度放到一行读到文件结束为止。如果你照着一个固定格式写换到别的题库很可能读入错乱。我的习惯是 main 里写 while (cin n)然后接着读 n 个数如果遇到不给 n 的版本再把输入改成全部读入到 vector 直到 EOF。也可以写一个小工具函数自动判断下一行不过小题没必要灵活处理即可。5.4 理解不了“最小路径覆盖”时的替代思路如果你还没学二分图匹配看到最小路径覆盖这个标签可能会慌。实际上这道题完全不需要匹配知识你只要掌握贪心加 LIS 就够。题目如果需要你输出具体方案才需要模拟 multiset 贪心并给每套系统编号。如果题目真的改成一般 DAG 的最小路径覆盖优先去补拆点加最大流或匈牙利算法。这时候你再回头看拦截导弹会觉得它其实是偏序集上的特例。先把特殊结论吃透再学通用方法比一上来就啃图论模板舒服很多。6. 从这道题向外走一类偏序问题的通用套路6.1 最长上升子序列的变体记忆法我把常见的 LIS 变体整理成一个记忆表原序列求严格上升用 lower_bound求不下降用 upper_bound求严格下降可以把数组反转或者反过来比较求不上升可以先取负再 upper_bound。本质上允许相等就比标准严格 LIS 多一档让二分边界向“大于等于/大于”偏移一点。不要死记结论要多想想含义。严格上升为什么 lower_bound因为遇到相等不能延长只能替换。不下降为什么 upper_bound因为遇到相等可以延长所以要跨过相等元素。想明白了换到下降、不上升也一样能推。6.2 Dilworth 定理还能解决哪些问题除了导弹拦截Dilworth 定理在很多看似无关的题里都有用。比如说平面上给你一堆点问最少用多少条“非递减”折线覆盖所有点或者说一个任务序列要分成最少多少个单调不增的堆又或者俄罗斯套娃问题本质都是链覆盖和反链。套路是先定义偏序关系再判断要求的是链还是反链最后转化成 LIS 或最大匹配。90% 的偏序题最后都会落到这两个点上。你多练几道不同外壳的题就会发现内核完全一致。6.3 想输出具体拦截方案贪心加记录即可题目如果只问数量上面的 LIS 代码就够了。但有些版本会要求输出每套系统拦了哪几枚导弹这时候就要回到 3.1 节的 multiset 贪心给每个系统维护一个 id。每次找到合适的系统后把当前导弹加入该系统的方案尾部并把它的最新拦截高度更新成 x。我第一次实现方案输出时没有记录 id只输出每套系统的最后高度结果完全看不出顺序。踩过这个坑后我的做法是维护一个 vectorvector plans和 multiset 平行更新。虽然代码会变长但逻辑很直接不容易错。最后说一点个人体会这种一题双问的题最怕的不是不会算法而是第一问和第二问的解法互相污染。我的应对方式是给两个函数起非常明确的名字一个叫 longestNonIncreasing一个叫 longestStrictIncreasing并且在注释里写清楚各自用什么二分边界。代码写完之后先跑边界用例再跑样例最后拿朴素 DP 对拍一遍。这套流程走下来拦截导弹这题才算真正吃透了。