一、LIS 是什么LISLongest Increasing Subsequence给定序列 a找出最长的一段子序列满足严格单调递增a[i]a[j],ij。子序列不要求连续但顺序不变。常见变种严格上升a[i]a[j]不下降a[i]≤a[j]严格下降 / 不下降把符号反过来即可。二、问题模型一句话输入a[1..n]输出最长上升子序列长度有时也要输出方案。三、解法 1朴素 DPO(n^2)入门必会1. 定义状态dp[i]以 a[i]结尾的 LIS 长度。2. 转移方程dp[i]max{dp[j]1∣ji, a[j]a[i]}初始dp[i]1每个元素自己是长度 1 的 LIS。3. 答案max{dp[1..n]}。4. 代码Cint lis_dp(const vectorint a) { int n a.size(), ans 1; vectorint dp(n, 1); for (int i 1; 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]); return ans; }5. 适用范围n≤10^3 完全够用数据再大就会超时。四、解法 2贪心 二分O(nlogn)竞赛最优1. 核心思想极关键维护一个数组 ff[k] 表示长度为 k1 的上升子序列的 “最小末尾”。目的让末尾尽可能小为后面元素留出更大空间从而得到更长序列。遍历 a[i]若 a[i]f.back()直接接入长度 1。否则在 f 中找到第一个≥a[i]的位置替换为 a[i]保持序列性质不影响最长长度。最终 f 的长度就是 LIS 长度。2. 为什么正确因为我们维护的是 “所有长度为 k 的上升子序列的最小结尾”这样未来任何新元素能接上去的概率最大。3. 代码C严格上升int lis_optim(const vectorint a) { vectorint f; for (int x : a) { auto it lower_bound(f.begin(), f.end(), x); if (it f.end()) f.push_back(x); else *it x; } return f.size(); }4. 若求 “不下降”a[j]≤a[i]把lower_bound换成upper_boundauto it upper_bound(f.begin(), f.end(), x);五、LIS 常见变种导弹拦截 / 套路模板1最长不上升子序列LNIS要求 a[j]≥a[i]维护单调不上升数组 f二分找第一个小于x 的位置用greaterint lnis(const vectorint a) { vectorint f; for (int x : a) { auto it upper_bound(f.begin(), f.end(), x, greaterint()); if (it f.end()) f.push_back(x); else *it x; } return f.size(); }2最长严格下降同理维护单调下降数组用lower_bound配合greater。六、经典应用题导弹拦截 P1020题目两问一套系统最多拦截多少最长不上升子序列最少需要多少套根据 Dilworth 定理等于最长严格上升子序列长度所以代码直接套用上述模板两问分别求即可。七、避坑清单笔试常错初始化不能为 0dp [i] 初始 1f 为空。区分严格 / 不下降lower_bound/upper_bound别搞反。比较器降序变种必须用greaterint()。答案是全局 maxO (n²) 答案是 max (dp)O (n log n) 答案是 f.size ()。八、总结背这句就够LIS 最长上升子序列朴素 DPO(n2)求以每个结尾的最长贪心 二分O(nlogn)维护 “长度为 k 的最小末尾”变种只改比较器和二分条件套路完全一样