P14970 『GTOI - 2A』睡眠质量这道题我是补榜的时候顺手做掉的。题面不长初看特别像一道区间贪心实际上手之后才发现不是那么回事因为这道题让选的是带权区间求的是“总质量最大”。如果一路按着“选最多不重叠区间”的老经验走样例能骗过你交上去就会挂在一片 WA 里。这篇文章我会把从题意建模、两版 DP 推导、二分优化到最终 AC 的完整过程都写清楚你自己也能照着推一遍。适合刚学动态规划、想搞懂“加权区间调度”模型的选手也适合想看看这类题怎么从 O(N²) 优化到 O(N log N) 的人。1. 题意理解与模型建立1.1 把“睡眠”翻译成数学语言题目背景不需要过度解读核心信息就一句话你收到了 n 条睡眠建议每条建议表示“如果在时间段 [l_i, r_i] 内睡觉可以获得质量 w_i”最终的睡眠计划必须保证任意两段被选中的睡眠时间不重叠目标是让总质量最大。这里的关键点是“质量 w_i”和区间长度没有必然关系。有的区间短但质量高有的区间长反而质量低所以不能用长度当作价值也不能想当然地按“谁长选谁”来做。换句话说这道题输入的是若干个带权区间要求选一个两两不相交的子集使权值和最大。这就是经典的 weighted interval scheduling国内教材里一般叫“带权区间调度”。建模之后问题变成有 n 个区间每个有左端点 l、右端点 r、权值 w任取两个区间 i、j若被同时选中必须满足 r_i ≤ l_j 或 r_j ≤ l_i这里先按允许首尾相接的规则来最大化选中区间的 w 之和。看到这里如果你第一反应是“不重叠选最多区间按右端点排序然后贪心”说明老题做多了。那个贪心只对单位权重有效w_i 一上强度就废。1.2 小数据暴力怎么做在推正式做法之前先想一个任意数据范围下通吃的暴力能帮自己确认题意没理解偏。n 非常小的时候可以直接枚举每个区间选或不选检查选出来的集合内所有区间是否两两不相交复杂度 O(2^n × n)毫无技术含量但能当对拍器。稍微聪明一点是 dfs 按顺序搜每次进入下一个与当前已选最后一个区间不冲突的区间。这个暴力的用处在于等正解写完之后可以随机造小数据反复对拍验证二分查找和 DP 的下标细节没写错。我实际做题时是先把暴力写好再开始推正解的尤其是在区间能不能“无缝衔接”这种边界规则上没有暴力对照很容易被自己绕晕。1.3 贪心为什么不行很多初学者卡在“为什么不直接贪心”上。举一个三区间反例就明白了区间 A [1, 4]质量 6区间 B [3, 6]质量 7区间 C [5, 8]质量 6。按“选择结束时间最早的区间”的经典贪心会先选 A然后因为 C 与 A 不冲突就选 C总质量 12。但最优解其实是选 B 和 C总质量 13这两个区间也不重叠。所以只看“结束早”或者“结束早并且权值大”都可能丢掉跨过当前选择点的更优组合。根本原因在于带权区间问题具有明显的“决策之后影响后续”的结构选不选当前区间会改变下一个可选区间的起点范围。当一个决策会影响未来状态时就要往动态规划上想而不是继续加贪心条件硬救。2. 从 O(N²) DP 到 O(N log N)2.1 经典状态定义先把所有区间按右端点从小到大排序。右端点相同的可以按左端点随便排不影响正确性。设 dp[i] 表示“前 i 个区间排完序后能获得的最大总质量”注意这里的“前 i 个”指的是排完序后的前 i 个不是原始输入的前 i 个。dp[0] 0 表示一个都不选。对于第 i 个区间为了方便用 1-index 描述排序后的下标从 1 开始它只有两种归宿不选它那么继承前 i-1 个区间的答案dp[i] dp[i-1]选它那么需要保证前面选的区间都和它不重叠因此要从“右端点不超过当前左端点”的前缀里去挑最好的dp[i] dp[p_i] w_i。这里的 p_i 是一个非常关键的量它是满足 r_p ≤ l_i 的最大下标。换句话说在前 i-1 个区间里只有前 p_i 个区间有可能和当前区间同时被选中因为排序保证右端点越靠后的区间结束得越晚。2.2 朴素 O(N²) 转移如果不会二分p_i 可以直接暴力往前扫一边扫一边维护前缀最大值于是得到 O(N²) 的做法for (int i 1; i n; i) { dp[i] dp[i - 1]; for (int j i - 1; j 1; j--) { if (a[j].r a[i].l) { dp[i] max(dp[i], dp[j] a[i].w); break; } } }但是注意这个“找到第一个满足条件的 j 就 break”其实是有问题的因为排序只保证了右端点单调dp[j] 并不会因为 j 增大而一定更大。正确写法是扫完所有 j取 dp[j] w_i 的最大值。由于 p_i 是所有满足条件的下标里最大的那一个而 dp 又具备单调不减的性质dp[i] ≥ dp[i-1]所以最优的 j 就是满足条件的最大的 j也就是 p_i。这样才可以在找到第一个满足条件的 j 后直接 break。想通这个单调性后面二分的依据就落地了。数据范围一大O(N²) 肯定过不了n 给到 2×10⁵ 时平方复杂度直接爆炸必须把“找 p_i”降到 O(log N)。2.3 二分查找加速因为区间已经按右端点排序于是所有 r 值存在一个单调数组里。对于当前区间的左端点 l_i我们要找“最后一个右端点 ≤ l_i 的位置”。直接调用标准库里的 upper_boundint pos upper_bound(rList.begin(), rList.end(), l_i) - rList.begin();upper_bound 返回的是第一个“大于 l_i”的迭代器位置所以 pos 恰好就是右端点 ≤ l_i 的区间数量。接着用 dp[pos] 转移到当前区间因为 dp[pos] 已经包含了排序后前 pos 个区间的最优值。这套东西学过 STL 的选手应该秒懂但新手很容易把 upper_bound 和 lower_bound 用混。在“允许首尾相接”的规则下必须用 upper_bound如果题目规定“下一段必须在当前段结束后才开始严格大于才不冲突”那就要用 lower_bound让右端点等于左端点的那些区间也被排除。同样一个二分规则一变就要换函数这是本题最容易出问题的地方之一。2.4 转移方程与正确性完整转移方程如下dp[i] max(dp[i - 1], dp[upper_bound(rList, a[i].l)] a[i].w)正确性可以这样想dp[i] 的最优方案中第 i 个区间要么不选此时最优就是 dp[i-1]要么选此时所有能和它共存的区间一定来自“前 p_i 个区间”它们最优总和是 dp[p_i]。由于排序不改变区间集合只是调整了考虑顺序所以每个子问题的解都是原问题某个前缀的最优解最优子结构成立。2.5 复杂度分析排序 O(N log N)二分在循环内执行 N 次每次 O(log N)总体 O(N log N)空间 O(N)。对 2×10⁵ 数据量来说这个复杂度非常宽裕。如果出题人把 w_i 和端点的范围再拉大最优答案可能超过 int所以一眼就要把 dp 数组、权值、答案全部开 long long。3. 完整代码实现与细节3.1 结构体与排序写法设计结构体时我习惯先把 l、r、w 三个字段放一起然后单独开一个 vector 存排序后的右端点方便二分。排序的规则写右端点升序端点相等时不用特殊处理因为 dp 的单调性不受影响。#include bits/stdc.h using namespace std; struct Sleep { long long l, r; long long w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorSleep a(n); for (int i 0; i n; i) { cin a[i].l a[i].r a[i].w; } sort(a.begin(), a.end(), [](const Sleep x, const Sleep y) { return x.r y.r; }); vectorlong long rList(n); for (int i 0; i n; i) { rList[i] a[i].r; } vectorlong long dp(n 1, 0); for (int i 1; i n; i) { dp[i] dp[i - 1]; long long curL a[i - 1].l; long long curW a[i - 1].w; int pos upper_bound(rList.begin(), rList.end(), curL) - rList.begin(); dp[i] max(dp[i], dp[pos] curW); } cout dp[n] \n; return 0; }代码量很短只有二十几行但这二十几行背后的模型和边界细节一点都不少。我提交时就是在这个基础上加上 long long 和二分边界修正后过的。3.2 下标对应关系这段代码里最容易看晕的是 dp 的下标和结构体数组下标差 1 的问题。排序后第 i 个区间存在 a[i-1] 里dp[i] 表示前 i 个区间a[0] 到 a[i-1]的最优值dp[pos] 则代表前 pos 个区间的最优值而 pos 本身是 upper_bound 算出来的“右端点 ≤ curL 的区间数量”。举个例子假设 rList {3, 5, 6, 8}当前区间左端点 curL 5。upper_bound 找到第一个大于 5 的元素也就是 6返回下标 2代表 rList[0]、rList[1] 这两个右端点都是 ≤ 5 的pos 2dp[2] 恰好就是前两个区间的最优值。这个对应关系一旦理顺代码基本不会写错。3.3 样例推演给一组小样例[1, 3]w 4[2, 5]w 3[4, 6]w 5[5, 8]w 2排序后按右端点顺序就是 1、2、3、4 四个区间rList {3, 5, 6, 8}。dp[1]不选区 1 是 0选区 1 时 pos upper_bound 找右端点 ≤ 1返回 0dp[0] 4 4所以 dp[1] 4。dp[2]继承 dp[1] 4选区 2左端 2时右端点 ≤ 2 的区间不存在pos 0dp[0] 3 3仍为 4。dp[3]继承 4选区 3左端 4时upper_bound 在 {3, 5, 6, 8} 中找第一个大于 4 的元素是 5下标 1pos 1dp[1] 5 9所以 dp[3] 9。dp[4]继承 9选区 4左端 5时upper_bound 找第一个大于 5 的元素是 6下标 2pos 2dp[2] 2 6不更新所以最终答案是 9。最优选择是 [1, 3] 和 [4, 6]总质量 9。整个推演过程其实就展示了这个 DP 每一步都在考虑“前面能接什么”。3.4 内存与输入加速这道题内存很宽裕三个 vector 加起来都不到 8MB。不过我还是开了 ios::sync_with_stdio(false) 和 cin.tie(nullptr)主要防止输入量一大之后 iostream 默认的同步机制拖慢速度。虽然 2×10⁵ 的数据量理论上 cin 也能过但竞赛环境下多一重保障总没坏处。4. 实测中的坑与排查方法4.1 区间接壤到底算不算重叠这是我在做这题时踩得最深的一个坑。题目背景是“睡眠质量”人不能边睡边醒但前一段到 7:00 结束下一段从 7:00 开始这在常识里是能接上的所以大多数区间调度题用“r_i ≤ l_j”表示不冲突。但也有出题人会写“两个时间段不能有任何重合时刻”这时就变成 r_i l_j 才算不冲突。这两种规则在二分查找里对应不同函数允许接壤用 upper_bound(rList, l)因为右端点等于 l 的区间要算进可转移前缀不允许接壤用 lower_bound(rList, l)因为右端点等于 l 的区间必须被排除在外。我不建议靠“回忆题目原话”来猜正确做法是先看样例。题目样例不会只给一组刚好不触发边界争议的数据如果它给了 [3, 5] 和 [5, 7] 同时被选说明可以首尾相接如果答案里从没出现这种组合就要再读一遍“不重合”三个字的定义。4.2 long long 溢出不能含糊w_i 如果给到 10⁹ 级别选 n 个区间虽然不可能全选区间重叠限制了数量但选一万个就能到 10¹³int 远远不够。我见过有人结构体里 l、r 用 long longw 和 dp 却用 int样例能过大测试点直接爆这种低级失误特别可惜。另外在 max 函数里也不要瞎转类型直接让 w 和 dp 都是 long long转移时隐式提升省得调半天发现是溢出问题。4.3 二分结果 pos 可能等于 i一个容易被忽视的边界是当前区间的左端点很大以至于前面所有区间的右端点都 ≤ 它。此时 upper_bound 返回 n也就是说 pos 可以等于当前区间编号之前的最大值 n而不是限制在 i-1 内。好在 dp[pos] 不会访问到未计算的位置吗如果当前处理到第 i 个区间pos 最多是 n但 dp[n] 在后面才会算到这里是不是会出错实际上不会。因为按右端点排序后当前区间的右端点一定大于等于它自己的左端点所以右端点 ≤ 左端点的区间编号最多到 i-1不可能包含当前区间自己。pos 的上界自然被限制为 i-1读者可以在本地随便造数据验证这条性质。4.4 排序稳定性与 pair 的习惯有人喜欢把区间存成 pairlong long, long long第一关键字右端点第二关键字左端点。这样排序没问题但取区间时得用 a[i-1].second 当左端点写多了容易把 first、second 搞反。我最后选择了结构体 自定义 lambda代码可读性更好以后查错也方便。这个纯属个人习惯并不影响性能。4.5 常见错误速查表错误现象可能原因解决办法小样例全过大样例 WAdp、w 用了 int溢出全部换 long long只有边界数据错upper_bound / lower_bound 用反确认接壤规则换对应二分答案永远等于所有 w 之和没做重叠判断检查 p_i 找的是否是右端点 ≤ 左端点排序后答案和没排序一样用了原始下标做 dp严格按下标顺序转移有时会访问 dp[-1]下标从 0 开始写还没统一统一用 1-index 的 dp5. 变体题目与延伸思考5.1 要求输出方案怎么办很多变体不会只让输出最大值还会让输出选了哪些区间。做法也不难开一个 pre 数组记录每一步是从哪里转移过来的。如果 dp[i] dp[i-1]说明第 i 个区间不选pre[i] i-1如果 dp[i] dp[pos] w_i说明选了第 i 个区间pre[i] pos。最后从 n 往前跳 pre把所有选中区间的原始编号收集起来反转输出就行。这算是这道题最常见的加码形式。5.2 如果端点范围很小如果 l、r 的范围很小比如都在 10⁶ 以内还可以用“线段树 扫描”的姿势。把区间按左端点排序从右往左做每次查询 [r1, maxTime] 区间里的最大值来更新当前位置。或者直接对时间轴离散化在线段树上做“单点取 max、区间查询 max”这就是这一类题的另一个经典写法。不过对本题的约束来说排序 二分已经足够没必要强行上树。5.3 如果权值可以是负数有些变体会让 w_i 出现负数这时“选”不一定比“不选”好但转移方程本身不需要改因为 max(dp[i-1], dp[pos] w_i) 已经包含“不选它”的情况负数权值的区间自然会被跳过。但如果题目要求“必须选出至少一段睡眠”那就需要额外处理把不能选的情况设成负无穷而不是默认 dp[0] 0。这类细节要根据具体题面来不可照搬模板。5.4 同类型的题目印象加权区间调度这套模型在 OI 和面试题里都常见核心就是“按一端排序 找前缀最优 二分优化”。你把这个模板吃透之后再遇到“会议室预订最大收益”“任务调度最多报酬”这类问题基本就是改个输入结构的事。很多时候看起来千变万化的题底子都是同一个 DV。我个人做完这题最大的体会是不要看到区间就条件反射贪心先停下来想想“当前决策会不会影响未来”。会就考虑 DP不会才轮到贪心登场。这道睡眠质量题名字起得有点迷惑性实际上是一道非常标准的思维练习题值得反复咀嚼。