企业官网建设流程全解析

第一次在题目列表里看到[SSL1082] 拦截导弹，我还以为又是一道入门 DP。后来仔细一读，才发现它把两个经典问题绑在一起：先让你算最长不上升子序列，再让你算最少需要的拦截系统数量，后者在不少资料里被标成最小路径覆盖。这两个标签放在同一道题里，看起来很像，其实思维方式完全不同。如果你已经会第一问，却被第二问绕进去，那这篇就是为你准备的。

题面的核心是：一枚枚导弹按顺序飞来，每枚有高度 h。一套拦截系统发射后，后续每发炮弹的高度不能高于前一发，也就是系统拦截的导弹高度序列必须不上升。第一问问：给定整个序列，最多能拦下多少枚（允许跳着拦，但必须按来的顺序）；第二问问：若要全部拦完，最少需要多少套系统。第一问求的是“从一个序列中选一个最长子序列”，第二问求的是“对整个序列做最优划分”，前者是长度，后者是系统数量，两者的答案计算方式并不一样。

很多人把这题当成两道题分别套模板，结果第一问用最长不上升，第二问莫名奇妙也想用不上升，最后全错。实际上第二问的答案是最长严格上升子序列长度。不理解背后原因的话，基本只能靠背结论，换一道题就不会了。下面我从题意、理论、代码、排错四个角度，把这道题彻底拆开。

1. 先看懂这道题：两个问题，两种算法思想

1.1 题面在说什么

先明确输入输出。通常第一行是导弹数量 n，第二行是 n 个高度值。你需要输出两行：第一行是最长不上升子序列长度，第二行是最少系统数。也就是说，题目要你同时解决两个独立的优化问题，但它们建立在同一个序列上，所以解题时很容易混在一起。

第一问可以理解成：在导弹序列中选一个子序列，允许跳着选，但保持原始顺序，选出的高度序列要满足“后一个不超过前一个”，也就是 h[i] >= h[j]（i 在 j 前面）。问这个子序列最长能有多长。这是经典的最长不上升子序列问题，一般写成 LNDS（Longest 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，第二发高度 100，100 <= 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] = 1；dp[1] = 2（389 >= 207）；dp[2] = 3（389 >= 155，207 >= 155）；dp[3] = 2（只有 389 >= 300，207 和 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 几乎一样。维护一个单调不降的数组 d，d 的长度表示当前最长长度。每遇到一个 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 的变化如下。

注意第 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 C++17 实现，双问一次跑完

下面这份代码是我自己常用的版本，输入第一行为导弹数量 n，第二行为 n 个高度。两个问题分别用一个函数，全部用二分，O(n log n)。

#include <bits/stdc++.h> using namespace std; int longestNonIncreasing(const vector<int>& a) { vector<int> 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 vector<int>& a) { vector<int> 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) { vector<int> 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 边界用例与结果验证

我把常用测试数据整理成一张表，跑代码之前先对一遍。

空输入如果按 while(cin>>n) 读不到 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，只输出每套系统的最后高度，结果完全看不出顺序。踩过这个坑后，我的做法是维护一个 vector<vector > plans，和 multiset 平行更新。虽然代码会变长，但逻辑很直接，不容易错。

最后说一点个人体会：这种一题双问的题，最怕的不是不会算法，而是第一问和第二问的解法互相污染。我的应对方式是给两个函数起非常明确的名字，一个叫 longestNonIncreasing，一个叫 longestStrictIncreasing，并且在注释里写清楚各自用什么二分边界。代码写完之后，先跑边界用例，再跑样例，最后拿朴素 DP 对拍一遍。这套流程走下来，拦截导弹这题才算真正吃透了。