【数据结构与算法】LIS专项练习

LIS 专项练习题目编号说明【模板】最长上升子序列B3637纯LIS模板n≤10⁵用二分导弹拦截P1020LIS 贪心经典题合唱队形P1091LIS LDS 组合友好城市P2782排序后转LIS1.#includeiostream #includevector using namespace std; int main() { int n;cinn; vectorinta(n); for(int i0;in;i) { cina[i]; } vectorinttail; for(int i0;ia.size();i) { int xa[i]; auto itlower_bound(tail.begin(),tail.end(),x); if(ittail.end()) { tail.push_back(x); } else *itx; } couttail.size()endl; return 0; }最长上升子序列LIS题解与思路总结这道题本质上是一个非常经典的最长上升子序列问题给定一个长度为 n 的序列要求在不改变原有顺序的情况下选出一些元素使得它们严格递增并且长度尽可能长。很多人一开始会想到用动态规划去做定义 dp[i] 表示以第 i 个元素结尾的最长上升子序列长度然后枚举 ji如果 a[j]a[i] 就更新 dp[i]max(dp[i],dp[j]1)这种做法是完全正确的但是时间复杂度是 O(n²)在数据范围稍大时就会比较吃力而这道题的更优解法是利用“二分贪心”的思想将复杂度优化到 O(n log n)你写的代码正是这一种。核心在于维护一个数组 tail它并不是实际的上升子序列而是一个“辅助数组”用于记录当前每种长度的上升子序列所能达到的最小结尾值也就是说 tail[i] 表示长度为 i1 的上升子序列中结尾最小的那个值这一点非常关键因为“结尾越小未来越容易接上更大的数”这就是贪心的依据接下来我们遍历原数组中的每一个元素 x用 lower_bound 在 tail 中找到第一个大于等于 x 的位置如果找不到说明 x 比当前所有结尾都大可以直接接在最后使序列长度增加如果找到了就用 x 去替换那个位置的值这一步看起来像是“破坏了原来的序列”但实际上是在优化结尾让当前长度的子序列更“优质”从而为后续扩展创造更好的条件最终 tail 的长度就是最长上升子序列的长度。举一个简单的过程来理解比如序列 1 2 4 1 3 4一开始 tail 为空读到 1 就变成 [1]读到 2 变成 [1,2]读到 4 变成 [1,2,4]再读到 1 时会替换第一个位置tail 仍然是 [1,2,4]读到 3 时替换 4 变成 [1,2,3]最后读到 4 变成 [1,2,3,4]长度为 4这就是答案需要特别注意的是这里必须使用 lower_bound即找第一个大于等于的位置因为题目要求是严格递增如果换成 upper_bound 就会变成允许相等的“非严格递增”结果会出错另外 tail 数组本身并不是最终的子序列只是一个中间结构这一点也经常被误解。总结来说这道题的关键不在代码本身而在于理解“用一个数组维护最优结尾”的思想本质上是用二分查找不断压缩状态从而把原本 O(n²) 的问题优化到 O(n log n)这也是很多高级算法题中非常常见的一种套路。2.#includeiostream #includevector #includealgorithm using namespace std; int main() { int x; vectorintarr; while(cinx) { arr.push_back(x); } reverse(arr.begin(),arr.end()); vectorinttail; for(int i0;iarr.size();i) { int xarr[i]; auto itupper_bound(tail.begin(),tail.end(),x); if(ittail.end()) { tail.push_back(x); } else *itx; } couttail.size()endl; reverse(arr.begin(),arr.end()); vectorintg; for(int i0;iarr.size();i) { int xarr[i]; auto itlower_bound(g.begin(),g.end(),x); if(itg.end()) { g.push_back(x); } else *itx; } coutg.size()endl; return 0; }导弹拦截P1020LIS与贪心的经典双解法这道题是一个非常经典的“最长上升子序列变形题”但它的巧妙之处在于同一组数据需要你求两个不同的问题而且这两个问题刚好分别对应两种LIS模型如果你只是会套模板很容易只做对一半但如果理解了本质其实就是一题双解。题目大意是给出一串导弹高度系统有一个限制后发射的导弹拦截高度不能高于前一个也就是说必须形成一个“不上升”的序列第一个问题是求一套系统最多能拦截多少导弹本质上就是求最长非上升子序列第二个问题是如果要拦截所有导弹最少需要多少套系统这其实等价于把整个序列划分成若干个非上升子序列问最少划分数这个结论是等于最长上升子序列的长度。先说第一个问题你的做法是先 reverse 一下数组然后用 upper_bound 去做这一步其实是在把“最长非上升子序列”转化成“最长非下降子序列”因为反转之后原来的“从前往后不升”就变成了“从后往前不降”再用 upper_bound找第一个大于 x 的位置来维护 tail 数组这样就允许“相等”的情况存在得到的是一个非严格的单调序列长度这正好符合题目要求这一段代码本质就是一个“非严格LIS”只是方向变了一下。再说第二个问题很多人一开始会觉得要用贪心或者区间覆盖其实完全不用直接一个经典结论一个序列最少划分成多少个不下降或不上升子序列等于这个序列的最长上升子序列长度所以你后半部分代码直接对原数组做了一次标准的 LIS用的是 lower_bound找第一个大于等于 x 的位置维护的是严格递增序列这样得到的 g.size() 就是答案这个结论本质上来自“Dilworth定理”的思想但在竞赛中可以直接当结论用。你的整体代码其实非常标准前半段 reverse upper_bound 求的是“最长非上升子序列”后半段直接 lower_bound 求的是“最长上升子序列”两个答案分别对应题目的两个输出这里有一个很容易忽略的细节就是为什么一个用 upper_bound一个用 lower_bound本质区别在于前者允许相等非严格后者不允许相等严格递增这一点如果写反了答案会直接错。总结一下这道题可以用一句话概括第一个答案是最长非上升子序列第二个答案是最长上升子序列而代码实现上就是“reverse upper_bound”和“直接 lower_bound”两套模板如果你能把这题吃透其实就相当于把LIS的严格与非严格、以及序列划分这几个核心点都掌握了。在 LIS 问题中的用法最长上升子序列严格递增// 找第一个 ≥ x 的位置auto it lower_bound(g.begin(), g.end(), x);严格递增意味着不能有相等的元素所以替换时要把 ≥ x 的位置替换掉相等也要替换因为要保留最小的末尾最长不下降子序列允许相等// 找第一个 x 的位置auto it upper_bound(g.begin(), g.end(), x);允许相等所以相等时可以直接接在后面只有遇到 x 的才需要替换完整对照表子序列类型关系使用的函数比较器示例序列严格上升a[i] a[j]lower_bound默认1, 2, 3不下降a[i] ≥ a[j]upper_bound默认1, 1, 2严格下降a[i] a[j]lower_boundgreaterint()3, 2, 1不上升a[i] ≤ a[j]upper_boundgreaterint()3, 3, 23.#includeiostream #includevector using namespace std; int main() { int n; cin n; vectorintarr(n); for (int i 0; i n; i) cin arr[i]; vectorintL(n), R(n); for (int i 0; i n; i) { L[i] 1; for (int j 0; j i; j) { if (arr[j] arr[i]) { L[i] max(L[i], L[j] 1); } } } for (int i n-1; i0; i--) { R[i] 1; for (int j n-1; j i; j--) { if (arr[j] arr[i]) { R[i] max(R[i], R[j] 1); } } } int ans 0; for (int i 0; i n; i) { ans max(ans, L[i] R[i] - 1); } cout n - ans endl; return 0; }合唱队形P1091LIS的进阶应用双向DP详解这道题本质上是LIS的一个非常经典的变形如果你只会“单调上升”那这题会卡你一下但只要你理解“左右各做一遍LIS”就会发现它其实非常套路。题目要求从一排同学中删除最少的人使剩下的人形成“先严格递增再严格递减”的队形也就是一个“山峰形状”中间某个位置是最高点换个角度想与其考虑删谁不如考虑“最多能留下多少人”因为最后答案就是 n 减去这个最大人数而这个“最多能留下的人”本质就是一个最长的“先上升再下降”的子序列。怎么求这个序列呢关键就在于把问题拆开看对于每一个位置 i把它当作“山顶”那么左边必须是一个上升序列右边必须是一个下降序列于是我们定义两个数组L[i] 表示以 i 结尾的最长上升子序列长度R[i] 表示以 i 开始向右的最长下降子序列长度也可以理解为从右往左的LIS这样对于每个位置 i如果它作为山顶那么能形成的队形长度就是 L[i] R[i] - 1这里的 -1 是因为 i 被计算了两次。你的代码正是这样实现的前半部分双重循环在做一个经典的 LISO(n²)计算每个位置向左的上升序列长度后半部分从右往左再做一遍类似的过程计算每个位置向右的“下降序列”实际上写法还是 LIS只不过方向反了、比较符号一样最后枚举每个位置作为山顶取最大值 ans最终输出 n - ans就是最少需要出列的人数。举个例子理解一下比如序列 186 186 150 200 160 130 197 220对于某个位置比如 200它左边可以形成一个递增序列150 → 200右边可以形成一个递减序列200 → 160 → 130拼起来就是一个“山”我们就是在所有可能的山里找最高的那个需要注意的是这里用的是严格小于arr[j] arr[i]所以是“严格单调”如果写成 ≤ 就会出错。总结一下这道题的核心就是一句话枚举每个点作为峰值左边做LIS右边做LIS反向合并得到一个“最长双调子序列”最后用总人数减去这个长度就是最少删除人数这类题是LIS非常典型的拓展如果你掌握了这种“左右各算一遍再合并”的思路很多类似的“山形数组”“摆动序列”问题都会变得很简单。4.#includeiostream #includevector #includealgorithm using namespace std; typedef struct city { int north; int sourth; }; bool f(city a, city b) { return a.north b.north; } int main() { int n; cin n; vectorcityarr(n); for (int i 0; i n; i) { cin arr[i].north arr[i].sourth; } sort(arr.begin(), arr.end(), f); vectorinta; for (int i 0; i arr.size(); i) { a.push_back(arr[i].sourth); } vectorinttail; for (int i 0; i a.size(); i) { int x a[i]; auto it lower_bound(tail.begin(), tail.end(), x); if (it tail.end()) { tail.push_back(x); } else *it x; } cout tail.size() endl; }最多不相交航道问题从“画线不交叉”到LIS的一次转化这道题表面看是一个几何问题其实本质是一个非常经典的LIS模型属于“看起来不像LIS但最后一定是LIS”的那一类题。题目的意思是南北两岸各有一些城市每一对城市之间要连一条直线现在要求选出尽量多的连线并且保证这些线之间不能相交如果你真的在纸上画几条线很快就会发现一个规律两条线是否相交取决于它们在两岸的相对顺序是否一致。更具体一点如果我们把所有城市按“北岸坐标”从小到大排序那么对于任意两条线 i 和 ji 在前j 在后如果 south[i] south[j]那么这两条线是不会相交的反之如果 south[i] south[j]那它们就一定会交叉问题一下子就变成了在排序后的序列中找一个尽量长的“south递增子序列”。也就是说这道题可以转化为一句话先按北岸排序再在南岸上求最长上升子序列LIS。你的代码正是按这个思路来的先定义结构体存 north 和 south然后按 north 排序这一步是关键它保证我们只需要关心 south 的顺序接着把所有 south 提取出来变成一个一维数组最后在这个数组上跑一遍 LIS用的是 lower_bound 的 O(n log n) 写法tail 数组维护的是“长度为 k 的递增子序列中最小的结尾”每来一个数就用二分去更新它最终 tail 的长度就是答案。这里有一个细节很容易被忽略为什么一定要先按 north 排序因为如果不排序线的“左右顺序”是混乱的我们无法用一个简单的单调性来判断是否相交排序之后相当于我们固定了一侧的顺序另一侧只要保持递增就不会发生交叉。再换个更直观的理解方式把北岸当作横坐标把南岸当作纵坐标每一对城市就是一个点那么问题就变成了从这些点中选出最多的点使得它们的 x 和 y 都是递增的这其实就是二维偏序问题而它的经典解法就是“排序 LIS”。总结一下这题的核心套路先通过排序“消掉一个维度”把问题降成一维再在剩下的一维上做最长上升子序列只要你看到“不能交叉 / 不能相交 / 顺序不能乱”这一类描述就可以往这个方向去想基本八九不离十就是LIS了。