刷题刷到一道“最大覆盖问题”题号 8593名字平平无奇题干也很短大概意思是给一堆区间选 k 个让它们覆盖的总长度最长。第一反应是不是贪心我当时也是这么想的结果被一个五区间反例按在地上摩擦。后来发现这个题表面是个贪心选择题实际考的是把“覆盖”这件事抽象成集合模型之后如何设计状态和转移。这篇文章就把我从头到尾的推导、代码、优化、踩坑都写出来希望能帮你少走几次弯路。这篇内容适合三类人正在刷题准备算法面试的同学、搞 OI/ACM 的老兵、以及工作中偶然需要处理“选 k 个集合覆盖最多元素”这类优化问题的工程师。最大覆盖问题本身是 NP-hard 的这一点必须记住但是在特殊场景下比如集合是数轴上的区间时它可以被排序加动态规划精确求解。先把这个边界搞清楚后面所有操作才不会跑偏。1. 题面拆开看最大覆盖到底在覆盖什么1.1 把“覆盖”抽象成集合操作很多人看到“覆盖”两个字就开始往线段树、扫描线上想这没错但容易漏掉一个更本质的东西。最大覆盖问题最通用的描述是这样的有一个全集里面若干元素给你一堆子集每个子集覆盖其中一部分元素现在让你最多选 k 个子集目标是让这些子集的并集元素数量最大。落到区间题里全集就是数轴上的坐标点子集就是一个个区间 [l, r]元素数量可以理解成区间长度。选 k 个区间求并集长度最大。这个抽象非常重要因为一旦你把它写成集合操作就会发现“覆盖长度”就是并集大小而并集天然自带去重逻辑。两个区间重合的部分只算一次这个语感和“选中的区间长度加起来”完全不同很多初学者第一次 WA 就是栽在把区间长度直接相加。1.2 区间覆盖、点覆盖与集合覆盖的区别最大覆盖问题在竞赛里有几个常见马甲我列个表方便对照变体子集结构目标难度区间最大覆盖数轴上的区间选 k 个区间使并集长度最大区间结构可用 DP 精确求解点集最大覆盖每个集合是点集子集选 k 个子集使覆盖点数最多一般情况 NP-hard集合覆盖覆盖全部任意子集选最少子集覆盖全集NP-hard连近似都有限制注意集合覆盖和最大覆盖是“对偶”关系一个问最少用几个集合能盖满一个问用固定 k 个集合能盖多少。前者是 NP-hard后者同样也是 NP-hard。但是当子集结构退化成“数轴上连续的一段区间”时这个结构足够特殊才能用多项式 DP 解。1.3 数据范围暗示的算法方向竞赛题不会无缘无故给你一个奇怪的数据范围它们全是提示。我记得类似 8593 这种最大覆盖题常用数据范围分三档n 很小比如 n ≤ 20直接枚举子集或者状压 DP甚至暴力搜索都能过。n 在 10^3 级说明预期解法是 O(n^2 k) 或 O(nk log n) 级别的区间 DP。n 在 10^5 级且 k 很大通常不是让你求精确解而是让你用贪心拿近似分或者题目另有特殊性质比如所有区间长度相同、所有左端点有序等。拿到题先看数据范围再决定往哪个方向想。我当时看到 n、k 都在可承受范围内就知道这不是一个贪心题肯定有精确解。2. 贪心为什么在这里翻车一个反例与 NP-hard 的现实2.1 最自然的贪心策略大多数人遇到“选 k 个区间覆盖长度最大”的第一反应是每次选一个当前能带来最大新增覆盖长度的区间选完就把它覆盖的部分标记掉重复 k 次。这个策略不能说是错的它其实是最大覆盖问题经典近似算法 greedy 的一个实例理论保证是至少能拿到最优解的 1 - 1/e也就是大约 63%。问题在于竞赛题要的是精确解63% 这个近似比根本无法接受。你需要一个反例让自己彻底死心而不是在 WA 之后还继续加各种乱七八糟的修正。2.2 一个让贪心失效的构造我当时构造了一个非常小的例子只有 5 个区间选 k2区间 A[1, 100]长度 99区间 B[101, 101]长度 0可看作一个点区间 C[1, 50]长度 49区间 D[51, 100]长度 49区间 E[60, 70]长度 10贪心第一步会选 A因为新增长度 99 最大。选完之后 [1,100] 全被覆盖第二步无论选谁新增都是 0总覆盖 99。但最优解是选 C 和 D因为 C 覆盖 [1,50]D 覆盖 [51,100]两者不重叠并集长度 98比 99 小一点。这反例不够狠我换一个更极端的区间 A1 到 A50 都是互不重叠的小区间每个长度 2分散在数轴上。一个大区间 Big 覆盖了其中一半小区间但被覆盖的那一半小区间自身长度加起来有 60。选 k25 时贪心先选 Big因为新增 60 最大剩下还能选 24 个但 Big 已经把它覆盖的范围盖住了剩下的只能选没重叠的小区间总覆盖 60 少量而最优解是直接选那 25 个不相交的小区间总覆盖 50×2100。这个例子说明贪心只考虑当前一步的新增收益完全不会为了“未来 24 步”去牺牲当下一点点收益。这就是它翻车的根源。2.3 NP-hard 下界与近似比更深一层最大覆盖问题在一般情况下是 NP-hard这意味着不存在多项式时间内的精确算法除非 PNP。你也可以从另一个角度理解如果存在多项式算法那你就能拿它去解集合覆盖的判定问题也就是说有一个多项式归约链条存在。但这不代表工程里没法处理。贪心算法的近似比 1 - 1/e 已经很可观配合局部搜索和随机重启在中等规模数据上经常能逼近最优解。后面我会专门讲一般集合模型的启发式方案先回到区间这个特例因为区间结构可以拿到精确解。3. 区间版最大覆盖的精确解法排序配合动态规划3.1 按右端点排序的理由做区间 DP 第一步永远是排序。但按什么排序按左端点排序也可以但在这道题里按右端点排序才能让状态定义干净。原因很简单我们需要保证“当前并集的最右端”是已知的。如果所有区间按右端点从小到大排那么当你把第 i 个区间作为“已选区间中最后一个”时它的右端点 r_i 一定是整个并集的最右端。这样状态里就不用再单独记录当前并集延伸到哪了一维信息直接由下标 i 承担。排序的代码实现有一个细节右端点相同的情况下按左端点升序排。为啥因为右端点相同但左端点更大的区间一旦被选它一定被同右端点、左端点更小的区间完全包含对覆盖长度没有贡献。让左端点小的排在前面可以保证转移时新增长度不会被算错这个我放到最后一章单独讲。3.2 dp[i][j] 的状态设计与转移公式定义状态dp[i][j] 表示排序后的前 i 个区间中选出 j 个区间并且第 i 个区间一定被选的情况下能得到的最长覆盖长度。因为第 i 个区间是排序后右端点最大的所以这 j 个区间的并集右端点就是 r_i。初始化非常直接dp[i][1] r_i - l_i也就是说只选第 i 个区间覆盖长度就是这个区间本身的长度。转移是这道题的核心公式长这样dp[i][j] max(dp[p][j-1] add) 其中 p iadd r_i - max(l_i, r_p)这个 add 的含义是在已经选了 p 作为上一个“最后区间”的前提下新加入第 i 个区间能新增的覆盖长度。要分两种情况理解如果 r_p l_i说明第 i 个区间和之前的并集完全分离它是新开的一段新增长度就是 r_i - l_i。如果 r_p ≥ l_i说明第 i 个区间和之前的覆盖有重叠之前的并集已经覆盖到 r_p新增长度只有 r_i - r_p。这里为什么只用 r_p 判断因为 p 是上一个被选中的区间它保证之前选出的所有区间右端点都不超过 r_p所以并集最右端就是 r_p。即使之前某两个区间的拼接让覆盖向左扩展了不少也不会影响这次的新增长度因为新增只和最右端有关。3.3 为什么这个转移不会漏解我最开始担心一个问题万一最优解中第 i 个区间跟“上一个选中区间 p”并不相邻中间还隔着几个没被选的区间那 p 怎么能代表并集最右端答案是流动但不会漏解。因为不管中间隔着多少没被选的区间最优解中一定存在一个“按右端点排序后在 i 之前且离 i 最近的一个选中区间”。这个区间就是转移里的 p。dp[p][j-1] 已经涵盖了前 p 个区间内部随便怎么选的最优组合中间那些没选的区间根本不需要关心。换句话说我们只是把所有选中区间按右端点排序然后依次考虑相邻选中的两个区间之间如何累加新增长度。这是区间覆盖 DP 能成立的关键也是和贪心最大的区别贪心关注每一步DP 关注相邻状态之间的累积。4. 一套能直接提交的代码以及复杂度优化的两个方向4.1 朴素 C 实现先给一个直白版本复杂度 O(n²k)适合 n ≤ 500、k ≤ 100 左右的数据范围。思路清晰也方便和转移公式对照。#include bits/stdc.h using namespace std; using ll long long; struct Seg { ll l, r; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorSeg a(n); for (int i 0; i n; i) { cin a[i].l a[i].r; } sort(a.begin(), a.end(), [](const Seg x, const Seg y) { if (x.r ! y.r) return x.r y.r; return x.l y.l; }); const ll NEG -(1LL 60); vectorvectorll dp(n, vectorll(k 1, NEG)); ll ans 0; for (int i 0; i n; i) { dp[i][1] a[i].r - a[i].l; // 只选这一个区间 ans max(ans, dp[i][1]); for (int j 2; j k; j) { ll best NEG; for (int p 0; p i; p) { if (dp[p][j - 1] NEG) continue; ll add a[i].r - max(a[i].l, a[p].r); best max(best, dp[p][j - 1] add); } dp[i][j] best; ans max(ans, best); } } cout ans \n; return 0; }如果你读到这里建议手动跑一遍之前那个例子A[1, 10]B[5, 15]C[12, 20]按右端点排完是 A、B、Ck2 时答案应该是 18对应选 A 和 C。dp[C][2] dp[A][1] 20 - max(12, 10) 10 8 18。没问题。4.2 复杂度分析与线段树/二分优化朴素版为什么是 O(n²k)最外层枚举 i里面枚举 j再枚举 p。其实 j 的循环只有 k 层真正的大头是 for p 那一层。n 到 2000、k 到 200 就已经是 8 亿次操作C 会跑得很难看。优化方向是把内层 for p 这层消掉。看转移公式dp[i][j] max(dp[p][j-1] r_i - max(l_i, r_p))拆成两部分当 r_p l_i 时新增长度是 r_i - l_i这部分只要求 max(dp[p][j-1])其中 p 满足 r_p l_i。因为 r_p 是单调不减的可以二分出最后一个 r_p l_i 的位置再用前缀最大值数组查。当 r_p ≥ l_i 时新增长度是 r_i - r_p贡献是 dp[p][j-1] - r_p这部分用线段树维护区间最大值查询区间 [pos, i-1] 的最大值即可。优化之后复杂度是 O(nk log n)。代码会多一些但思路完全沿袭朴素版。我自己的经验是先写朴素版拿部分分或验证正确性再改优化版应付大数据。千万别一上来就写线段树写错一个维护逻辑比超时还难受。4.3 Python 验证版Python 跑同样 DP 在竞赛里通常会超时但用来做小数据验证非常合适。写一个清晰版def max_cover(segments, k): segs sorted(segments, keylambda x: (x[1], x[0])) n len(segs) NEG -10**18 dp [[NEG] * (k 1) for _ in range(n)] ans 0 for i in range(n): l, r segs[i] dp[i][1] r - l ans max(ans, dp[i][1]) for j in range(2, k 1): best NEG for p in range(i): if dp[p][j-1] NEG: continue add r - max(l, segs[p][1]) best max(best, dp[p][j-1] add) dp[i][j] best ans max(ans, best) return ans这段代码在本地测试时建议配合随机暴力对拍。我会在最后一章讲对拍脚本怎么写这里先记住一个原则DP 题不写对拍等于裸奔。5. 脱离区间后一般最大覆盖问题的启发式实战5.1 一般集合模型下的困境区间版能做 DP是因为区间之间有天然的“左右顺序”可以拿来设计状态。但如果你手里的数据不是区间而是一堆任意子集比如每个用户属于哪几个兴趣标签、每个广告位能触达哪些人群这就完全是最大覆盖问题。它在理论上是 NP-hard 的经典贪心算法也只能保证 1 - 1/e 的近似比。那工程里怎么解决我自己的答案是不要追求全局最优用贪心搭骨架再用局部搜索和随机重启把结果顶上去。这套组合拳在广告投放、特征选择、传感器布点这类场景里效果已经足够和精确解掰手腕。5.2 贪心 局部搜索 随机重启先说贪心骨架。每次从还没选的子集里挑一个能带来最多新增覆盖元素的集合选够 k 个为止。这步很快但是解的质量不稳定。然后做局部搜索随机从当前选中集合里拿掉一个再尝试放一个当前没被选的集合进去如果整体覆盖数变多就保留这次替换。这个动作反复做直到一轮里没有任何替换能让结果变好。最后是随机重启因为贪心起点和局部搜索都受初始集合顺序影响干脆随机打乱顺序多跑几轮每轮保留最好结果。我整理了一个最简单的实现模板直接用 Python 写import random def evaluate(sets, selected): cover set() for idx in selected: cover | sets[idx] return len(cover) def greedy_once(sets, k, order): selected [] covered set() for idx in order: if len(selected) k: break if sets[idx] - covered: selected.append(idx) covered | sets[idx] return selected def local_search(sets, k, selected): changed True while changed: changed False n len(sets) for i in range(len(selected)): for j in range(n): if j in selected: continue new_selected selected[:i] [j] selected[i1:] if evaluate(sets, new_selected) evaluate(sets, selected): selected new_selected changed True break if changed: break return selected def max_cover_heuristic(sets, k, rounds50, seedNone): if seed is not None: random.seed(seed) n len(sets) best_val 0 best_sel [] for _ in range(rounds): order list(range(n)) random.shuffle(order) sel greedy_once(sets, k, order) sel local_search(sets, k, sel) val evaluate(sets, sel) if val best_val: best_val val best_sel sel return best_val, best_sel这个版本直接可用但要注意如果每个子集特别大evaluate 每次都求并集会比较慢你可以事先把所有集合做成 Python frozenset或者用位集表示元素把并集操作压成位运算。竞赛里遇到 n10^5 级别的场景位集是最实用的优化。5.3 实用参数与调优经验随机重启轮数不是越多越好。我实测过对 100 个集合选 20 个这种规模20 到 50 轮的提升明显超过 100 轮收益就几乎见底了。真正影响效果的是局部搜索里的替换策略简单随机替换比按顺序扫描弱很多但扫描开销大得权衡。另一个经验贪心阶段每轮都重新计算“哪个集合新增最多”很费时间。可以用一个最大堆把每个集合当前的新增元素数放进去被选中集合覆盖掉一部分后只更新受影响的那几个集合。数据量大了以后这个优化能从 O(kn) 降到接近 O(k log n)前提是你维护好每个集合的“未被覆盖剩余元素”。6. 调试与提交中反复出现的问题6.1 端点开闭与重复区间区间覆盖题里最蠢也最常见的错误是端点开闭没搞清楚。题目如果说覆盖长度是 r - l那显然左闭右开或闭区间都无所谓因为长度都是 r-l。但如果你把坐标离散成点开闭不同会导致离散化结果差 1。另一个坑是完全相同的重复区间。去重还是不去重如果允许选“至少 k 个”或“最多 k 个”重复区间可以全去掉只保留一份。但如果题目要求恰好选 k 个重复区间可能是用来凑数的这时候不能去重。我建议看数据范围n 稍大时直接保留重复DP 会自动处理新增长度为 0 的情况不会错n 很大空间紧张时再考虑压缩。6.2 状态数组初值与“恰好 k 个”的处理dp 数组初始化成负无穷是必须的不是 0。因为某些 j 个区间的组合根本不存在比如 j5 但只看了 3 个区间这个状态就是非法的。如果初始化为 0转移时会把不可能的状态当成 0 参与计算污染答案。“最多 k 个”和“恰好 k 个”也要区分清楚。上面代码里我维护了 ans它取的是所有合法 dp[i][j] 的最大值这是“最多 k 个”的语义。如果你要恰好选 k 个最后就不要取全局 max而是只输出 dp[n-1][k] 这类值。竞赛题经常在这里埋坑。6.3 右端点相同时的排序细节我在第三章提过右端点相同必须按左端点升序排。再展开说下为什么假如两个区间右端点都是 10一个左端点是 1另一个左端点是 5。后者被前者完全包含。按右端点排完如果左端点大的排前面dp 转移时可能把“并集最右端”当成 10但实际最优并集最左端可以更靠左导致漏掉左侧延伸的覆盖长度。按左端点升序排能保证同一右端点下先出现的区间一定比后出现的区间覆盖范围更靠左后出现的区间要么被包含、要么向右延伸不了新增长度算 0 不会错。6.4 超时排查从 n²k 到 nk log n如果朴素版超时别急着换思路。先把内层循环里所有可以提出循环的常量提出来比如 a[i].r - max(a[i].l, a[p].r) 里 a[i].r 是定值这部分可以写成前缀最大值 后缀查询两个维护数组。我优化时踩过一个小坑前缀最大值数组要按右端点单调性维护而不是按下标直接无脑 minmax因为你二分的边界是 r_p l_i不能把所有 p 都一股脑塞进前缀。最后分享一个调试技巧写一个纯暴力枚举 C(n, k) 组合的脚本再写随机生成器用暴力结果当标准答案和 DP 结果对拍。区间规模控制在 10 以内、坐标范围控制在 20 以内跑个几千组随机数基本上几分钟内就能把所有边界错误暴露出来。这个习惯我保持了很多年几乎每次都能在提交前捞出一两个暗坑。
最大覆盖问题：从贪心失效到区间DP精确求解
刷题刷到一道“最大覆盖问题”题号 8593名字平平无奇题干也很短大概意思是给一堆区间选 k 个让它们覆盖的总长度最长。第一反应是不是贪心我当时也是这么想的结果被一个五区间反例按在地上摩擦。后来发现这个题表面是个贪心选择题实际考的是把“覆盖”这件事抽象成集合模型之后如何设计状态和转移。这篇文章就把我从头到尾的推导、代码、优化、踩坑都写出来希望能帮你少走几次弯路。这篇内容适合三类人正在刷题准备算法面试的同学、搞 OI/ACM 的老兵、以及工作中偶然需要处理“选 k 个集合覆盖最多元素”这类优化问题的工程师。最大覆盖问题本身是 NP-hard 的这一点必须记住但是在特殊场景下比如集合是数轴上的区间时它可以被排序加动态规划精确求解。先把这个边界搞清楚后面所有操作才不会跑偏。1. 题面拆开看最大覆盖到底在覆盖什么1.1 把“覆盖”抽象成集合操作很多人看到“覆盖”两个字就开始往线段树、扫描线上想这没错但容易漏掉一个更本质的东西。最大覆盖问题最通用的描述是这样的有一个全集里面若干元素给你一堆子集每个子集覆盖其中一部分元素现在让你最多选 k 个子集目标是让这些子集的并集元素数量最大。落到区间题里全集就是数轴上的坐标点子集就是一个个区间 [l, r]元素数量可以理解成区间长度。选 k 个区间求并集长度最大。这个抽象非常重要因为一旦你把它写成集合操作就会发现“覆盖长度”就是并集大小而并集天然自带去重逻辑。两个区间重合的部分只算一次这个语感和“选中的区间长度加起来”完全不同很多初学者第一次 WA 就是栽在把区间长度直接相加。1.2 区间覆盖、点覆盖与集合覆盖的区别最大覆盖问题在竞赛里有几个常见马甲我列个表方便对照变体子集结构目标难度区间最大覆盖数轴上的区间选 k 个区间使并集长度最大区间结构可用 DP 精确求解点集最大覆盖每个集合是点集子集选 k 个子集使覆盖点数最多一般情况 NP-hard集合覆盖覆盖全部任意子集选最少子集覆盖全集NP-hard连近似都有限制注意集合覆盖和最大覆盖是“对偶”关系一个问最少用几个集合能盖满一个问用固定 k 个集合能盖多少。前者是 NP-hard后者同样也是 NP-hard。但是当子集结构退化成“数轴上连续的一段区间”时这个结构足够特殊才能用多项式 DP 解。1.3 数据范围暗示的算法方向竞赛题不会无缘无故给你一个奇怪的数据范围它们全是提示。我记得类似 8593 这种最大覆盖题常用数据范围分三档n 很小比如 n ≤ 20直接枚举子集或者状压 DP甚至暴力搜索都能过。n 在 10^3 级说明预期解法是 O(n^2 k) 或 O(nk log n) 级别的区间 DP。n 在 10^5 级且 k 很大通常不是让你求精确解而是让你用贪心拿近似分或者题目另有特殊性质比如所有区间长度相同、所有左端点有序等。拿到题先看数据范围再决定往哪个方向想。我当时看到 n、k 都在可承受范围内就知道这不是一个贪心题肯定有精确解。2. 贪心为什么在这里翻车一个反例与 NP-hard 的现实2.1 最自然的贪心策略大多数人遇到“选 k 个区间覆盖长度最大”的第一反应是每次选一个当前能带来最大新增覆盖长度的区间选完就把它覆盖的部分标记掉重复 k 次。这个策略不能说是错的它其实是最大覆盖问题经典近似算法 greedy 的一个实例理论保证是至少能拿到最优解的 1 - 1/e也就是大约 63%。问题在于竞赛题要的是精确解63% 这个近似比根本无法接受。你需要一个反例让自己彻底死心而不是在 WA 之后还继续加各种乱七八糟的修正。2.2 一个让贪心失效的构造我当时构造了一个非常小的例子只有 5 个区间选 k2区间 A[1, 100]长度 99区间 B[101, 101]长度 0可看作一个点区间 C[1, 50]长度 49区间 D[51, 100]长度 49区间 E[60, 70]长度 10贪心第一步会选 A因为新增长度 99 最大。选完之后 [1,100] 全被覆盖第二步无论选谁新增都是 0总覆盖 99。但最优解是选 C 和 D因为 C 覆盖 [1,50]D 覆盖 [51,100]两者不重叠并集长度 98比 99 小一点。这反例不够狠我换一个更极端的区间 A1 到 A50 都是互不重叠的小区间每个长度 2分散在数轴上。一个大区间 Big 覆盖了其中一半小区间但被覆盖的那一半小区间自身长度加起来有 60。选 k25 时贪心先选 Big因为新增 60 最大剩下还能选 24 个但 Big 已经把它覆盖的范围盖住了剩下的只能选没重叠的小区间总覆盖 60 少量而最优解是直接选那 25 个不相交的小区间总覆盖 50×2100。这个例子说明贪心只考虑当前一步的新增收益完全不会为了“未来 24 步”去牺牲当下一点点收益。这就是它翻车的根源。2.3 NP-hard 下界与近似比更深一层最大覆盖问题在一般情况下是 NP-hard这意味着不存在多项式时间内的精确算法除非 PNP。你也可以从另一个角度理解如果存在多项式算法那你就能拿它去解集合覆盖的判定问题也就是说有一个多项式归约链条存在。但这不代表工程里没法处理。贪心算法的近似比 1 - 1/e 已经很可观配合局部搜索和随机重启在中等规模数据上经常能逼近最优解。后面我会专门讲一般集合模型的启发式方案先回到区间这个特例因为区间结构可以拿到精确解。3. 区间版最大覆盖的精确解法排序配合动态规划3.1 按右端点排序的理由做区间 DP 第一步永远是排序。但按什么排序按左端点排序也可以但在这道题里按右端点排序才能让状态定义干净。原因很简单我们需要保证“当前并集的最右端”是已知的。如果所有区间按右端点从小到大排那么当你把第 i 个区间作为“已选区间中最后一个”时它的右端点 r_i 一定是整个并集的最右端。这样状态里就不用再单独记录当前并集延伸到哪了一维信息直接由下标 i 承担。排序的代码实现有一个细节右端点相同的情况下按左端点升序排。为啥因为右端点相同但左端点更大的区间一旦被选它一定被同右端点、左端点更小的区间完全包含对覆盖长度没有贡献。让左端点小的排在前面可以保证转移时新增长度不会被算错这个我放到最后一章单独讲。3.2 dp[i][j] 的状态设计与转移公式定义状态dp[i][j] 表示排序后的前 i 个区间中选出 j 个区间并且第 i 个区间一定被选的情况下能得到的最长覆盖长度。因为第 i 个区间是排序后右端点最大的所以这 j 个区间的并集右端点就是 r_i。初始化非常直接dp[i][1] r_i - l_i也就是说只选第 i 个区间覆盖长度就是这个区间本身的长度。转移是这道题的核心公式长这样dp[i][j] max(dp[p][j-1] add) 其中 p iadd r_i - max(l_i, r_p)这个 add 的含义是在已经选了 p 作为上一个“最后区间”的前提下新加入第 i 个区间能新增的覆盖长度。要分两种情况理解如果 r_p l_i说明第 i 个区间和之前的并集完全分离它是新开的一段新增长度就是 r_i - l_i。如果 r_p ≥ l_i说明第 i 个区间和之前的覆盖有重叠之前的并集已经覆盖到 r_p新增长度只有 r_i - r_p。这里为什么只用 r_p 判断因为 p 是上一个被选中的区间它保证之前选出的所有区间右端点都不超过 r_p所以并集最右端就是 r_p。即使之前某两个区间的拼接让覆盖向左扩展了不少也不会影响这次的新增长度因为新增只和最右端有关。3.3 为什么这个转移不会漏解我最开始担心一个问题万一最优解中第 i 个区间跟“上一个选中区间 p”并不相邻中间还隔着几个没被选的区间那 p 怎么能代表并集最右端答案是流动但不会漏解。因为不管中间隔着多少没被选的区间最优解中一定存在一个“按右端点排序后在 i 之前且离 i 最近的一个选中区间”。这个区间就是转移里的 p。dp[p][j-1] 已经涵盖了前 p 个区间内部随便怎么选的最优组合中间那些没选的区间根本不需要关心。换句话说我们只是把所有选中区间按右端点排序然后依次考虑相邻选中的两个区间之间如何累加新增长度。这是区间覆盖 DP 能成立的关键也是和贪心最大的区别贪心关注每一步DP 关注相邻状态之间的累积。4. 一套能直接提交的代码以及复杂度优化的两个方向4.1 朴素 C 实现先给一个直白版本复杂度 O(n²k)适合 n ≤ 500、k ≤ 100 左右的数据范围。思路清晰也方便和转移公式对照。#include bits/stdc.h using namespace std; using ll long long; struct Seg { ll l, r; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorSeg a(n); for (int i 0; i n; i) { cin a[i].l a[i].r; } sort(a.begin(), a.end(), [](const Seg x, const Seg y) { if (x.r ! y.r) return x.r y.r; return x.l y.l; }); const ll NEG -(1LL 60); vectorvectorll dp(n, vectorll(k 1, NEG)); ll ans 0; for (int i 0; i n; i) { dp[i][1] a[i].r - a[i].l; // 只选这一个区间 ans max(ans, dp[i][1]); for (int j 2; j k; j) { ll best NEG; for (int p 0; p i; p) { if (dp[p][j - 1] NEG) continue; ll add a[i].r - max(a[i].l, a[p].r); best max(best, dp[p][j - 1] add); } dp[i][j] best; ans max(ans, best); } } cout ans \n; return 0; }如果你读到这里建议手动跑一遍之前那个例子A[1, 10]B[5, 15]C[12, 20]按右端点排完是 A、B、Ck2 时答案应该是 18对应选 A 和 C。dp[C][2] dp[A][1] 20 - max(12, 10) 10 8 18。没问题。4.2 复杂度分析与线段树/二分优化朴素版为什么是 O(n²k)最外层枚举 i里面枚举 j再枚举 p。其实 j 的循环只有 k 层真正的大头是 for p 那一层。n 到 2000、k 到 200 就已经是 8 亿次操作C 会跑得很难看。优化方向是把内层 for p 这层消掉。看转移公式dp[i][j] max(dp[p][j-1] r_i - max(l_i, r_p))拆成两部分当 r_p l_i 时新增长度是 r_i - l_i这部分只要求 max(dp[p][j-1])其中 p 满足 r_p l_i。因为 r_p 是单调不减的可以二分出最后一个 r_p l_i 的位置再用前缀最大值数组查。当 r_p ≥ l_i 时新增长度是 r_i - r_p贡献是 dp[p][j-1] - r_p这部分用线段树维护区间最大值查询区间 [pos, i-1] 的最大值即可。优化之后复杂度是 O(nk log n)。代码会多一些但思路完全沿袭朴素版。我自己的经验是先写朴素版拿部分分或验证正确性再改优化版应付大数据。千万别一上来就写线段树写错一个维护逻辑比超时还难受。4.3 Python 验证版Python 跑同样 DP 在竞赛里通常会超时但用来做小数据验证非常合适。写一个清晰版def max_cover(segments, k): segs sorted(segments, keylambda x: (x[1], x[0])) n len(segs) NEG -10**18 dp [[NEG] * (k 1) for _ in range(n)] ans 0 for i in range(n): l, r segs[i] dp[i][1] r - l ans max(ans, dp[i][1]) for j in range(2, k 1): best NEG for p in range(i): if dp[p][j-1] NEG: continue add r - max(l, segs[p][1]) best max(best, dp[p][j-1] add) dp[i][j] best ans max(ans, best) return ans这段代码在本地测试时建议配合随机暴力对拍。我会在最后一章讲对拍脚本怎么写这里先记住一个原则DP 题不写对拍等于裸奔。5. 脱离区间后一般最大覆盖问题的启发式实战5.1 一般集合模型下的困境区间版能做 DP是因为区间之间有天然的“左右顺序”可以拿来设计状态。但如果你手里的数据不是区间而是一堆任意子集比如每个用户属于哪几个兴趣标签、每个广告位能触达哪些人群这就完全是最大覆盖问题。它在理论上是 NP-hard 的经典贪心算法也只能保证 1 - 1/e 的近似比。那工程里怎么解决我自己的答案是不要追求全局最优用贪心搭骨架再用局部搜索和随机重启把结果顶上去。这套组合拳在广告投放、特征选择、传感器布点这类场景里效果已经足够和精确解掰手腕。5.2 贪心 局部搜索 随机重启先说贪心骨架。每次从还没选的子集里挑一个能带来最多新增覆盖元素的集合选够 k 个为止。这步很快但是解的质量不稳定。然后做局部搜索随机从当前选中集合里拿掉一个再尝试放一个当前没被选的集合进去如果整体覆盖数变多就保留这次替换。这个动作反复做直到一轮里没有任何替换能让结果变好。最后是随机重启因为贪心起点和局部搜索都受初始集合顺序影响干脆随机打乱顺序多跑几轮每轮保留最好结果。我整理了一个最简单的实现模板直接用 Python 写import random def evaluate(sets, selected): cover set() for idx in selected: cover | sets[idx] return len(cover) def greedy_once(sets, k, order): selected [] covered set() for idx in order: if len(selected) k: break if sets[idx] - covered: selected.append(idx) covered | sets[idx] return selected def local_search(sets, k, selected): changed True while changed: changed False n len(sets) for i in range(len(selected)): for j in range(n): if j in selected: continue new_selected selected[:i] [j] selected[i1:] if evaluate(sets, new_selected) evaluate(sets, selected): selected new_selected changed True break if changed: break return selected def max_cover_heuristic(sets, k, rounds50, seedNone): if seed is not None: random.seed(seed) n len(sets) best_val 0 best_sel [] for _ in range(rounds): order list(range(n)) random.shuffle(order) sel greedy_once(sets, k, order) sel local_search(sets, k, sel) val evaluate(sets, sel) if val best_val: best_val val best_sel sel return best_val, best_sel这个版本直接可用但要注意如果每个子集特别大evaluate 每次都求并集会比较慢你可以事先把所有集合做成 Python frozenset或者用位集表示元素把并集操作压成位运算。竞赛里遇到 n10^5 级别的场景位集是最实用的优化。5.3 实用参数与调优经验随机重启轮数不是越多越好。我实测过对 100 个集合选 20 个这种规模20 到 50 轮的提升明显超过 100 轮收益就几乎见底了。真正影响效果的是局部搜索里的替换策略简单随机替换比按顺序扫描弱很多但扫描开销大得权衡。另一个经验贪心阶段每轮都重新计算“哪个集合新增最多”很费时间。可以用一个最大堆把每个集合当前的新增元素数放进去被选中集合覆盖掉一部分后只更新受影响的那几个集合。数据量大了以后这个优化能从 O(kn) 降到接近 O(k log n)前提是你维护好每个集合的“未被覆盖剩余元素”。6. 调试与提交中反复出现的问题6.1 端点开闭与重复区间区间覆盖题里最蠢也最常见的错误是端点开闭没搞清楚。题目如果说覆盖长度是 r - l那显然左闭右开或闭区间都无所谓因为长度都是 r-l。但如果你把坐标离散成点开闭不同会导致离散化结果差 1。另一个坑是完全相同的重复区间。去重还是不去重如果允许选“至少 k 个”或“最多 k 个”重复区间可以全去掉只保留一份。但如果题目要求恰好选 k 个重复区间可能是用来凑数的这时候不能去重。我建议看数据范围n 稍大时直接保留重复DP 会自动处理新增长度为 0 的情况不会错n 很大空间紧张时再考虑压缩。6.2 状态数组初值与“恰好 k 个”的处理dp 数组初始化成负无穷是必须的不是 0。因为某些 j 个区间的组合根本不存在比如 j5 但只看了 3 个区间这个状态就是非法的。如果初始化为 0转移时会把不可能的状态当成 0 参与计算污染答案。“最多 k 个”和“恰好 k 个”也要区分清楚。上面代码里我维护了 ans它取的是所有合法 dp[i][j] 的最大值这是“最多 k 个”的语义。如果你要恰好选 k 个最后就不要取全局 max而是只输出 dp[n-1][k] 这类值。竞赛题经常在这里埋坑。6.3 右端点相同时的排序细节我在第三章提过右端点相同必须按左端点升序排。再展开说下为什么假如两个区间右端点都是 10一个左端点是 1另一个左端点是 5。后者被前者完全包含。按右端点排完如果左端点大的排前面dp 转移时可能把“并集最右端”当成 10但实际最优并集最左端可以更靠左导致漏掉左侧延伸的覆盖长度。按左端点升序排能保证同一右端点下先出现的区间一定比后出现的区间覆盖范围更靠左后出现的区间要么被包含、要么向右延伸不了新增长度算 0 不会错。6.4 超时排查从 n²k 到 nk log n如果朴素版超时别急着换思路。先把内层循环里所有可以提出循环的常量提出来比如 a[i].r - max(a[i].l, a[p].r) 里 a[i].r 是定值这部分可以写成前缀最大值 后缀查询两个维护数组。我优化时踩过一个小坑前缀最大值数组要按右端点单调性维护而不是按下标直接无脑 minmax因为你二分的边界是 r_p l_i不能把所有 p 都一股脑塞进前缀。最后分享一个调试技巧写一个纯暴力枚举 C(n, k) 组合的脚本再写随机生成器用暴力结果当标准答案和 DP 结果对拍。区间规模控制在 10 以内、坐标范围控制在 20 以内跑个几千组随机数基本上几分钟内就能把所有边界错误暴露出来。这个习惯我保持了很多年几乎每次都能在提交前捞出一两个暗坑。
