POI 2014 PTA-Little Bird：单调队列优化DP全面解析

最近刷题打卡正好轮到第2740天卡在洛谷 P3572 [POI 2014] PTA-Little Bird 这道题上。这是一道非常经典的 DP 优化题来自 POI 2014 现场赛洛谷题号 P3572。题面其实很朴素一只小鸟在树之间向前跳给你若干个跳跃能力 k问从第 1 棵树跳到第 n 棵树的最小疲劳值。朴素 DP 很好写但 n 最大可以到 1000000双重循环肯定超时所以核心就是用单调队列把每次转移优化到 O(1)整个问题做到 O(qn)。这道题我一开始被队列里的元素比较规则坑了大半个晚上今天把整个推导过程、C 实现、还有踩过的坑都整理出来希望对正在刷信奥 DP 专题的朋友有帮助。1. 题目背景与题意拆解PTA-Little Bird 到底在求什么1.1 POI 2014 是什么来头POI 是波兰信息学奥林匹克Polish Olympiad in Informatics的缩写题目质量在欧洲信奥圈子里口碑很高喜欢在简单背景里藏一个很深的模型。P3572 是洛谷收录时给的题号原名是 PTA-Little Bird题目本身只有一棵树的高度数组和若干次询问看起来像个签到题实际做起来会发现转移优化的门道不少。很多同学看到“POI 2014”会下意识觉得这是欧洲人的难题其实 Little Bird 并不是那种需要复杂数据结构的题它考察的就是最基础的 DP 优化手段——单调队列。适合已经学完线性 DP、正准备攻克单调队列优化的选手。如果你刚开始刷信奥题也可以先试着写暴力 DP拿部分分然后再把优化吃透。1.2 题面逐句拆开跳跃距离、疲劳值、询问先把题意翻译成可以直接建模的形式。有一排树编号从 1 到 n第 i 棵树的高度是 d[i]。小鸟一开始站在第 1 棵树上最终要跳到第 n 棵树上。每次跳跃只能向前跳并且最多跳过 k 棵树也就是说从当前树 i 跳到目标树 j 必须满足1 j - i k注意是“最多跳 k 棵”所以 j - i 不能超过 k但也允许只跳 1 棵。关键规则是疲劳值如果跳到的树高度不低于当前起跳的树那么这次跳跃会让小鸟疲劳值加 1如果跳到的树比当前这棵树矮那么疲劳值不变。用公式写就是从 j 跳到 i 的代价cost(j, i) 1 当 d[i] d[j]否则 cost(j, i) 0。最后题目会给 q 次询问每次给一个不同的 k要求输出对应的最小疲劳值。n 最大可以到 1000000q 最大是 25所以总运算次数大约在 2.5e7 这个量级C 是可以跑完的但前提是每个询问都要做到 O(n)不能带一个很大的常数。1.3 数据范围给我们的信号必须优化到 O(n) 级别如果直接用最朴素的动态规划对于每个位置 i要枚举前面所有可能的起跳点 j范围是 max(1, i-k) 到 i-1转移方程是这样的dp[i] min(dp[j] cost(j, i))最坏情况下 k 接近 n一层枚举就是 O(n^2)在 n1e6 时完全不可能通过。即使每个询问单独做也会爆炸。再看 q 只有 25这说明正解的复杂度大概率是 O(qn) 或者 O(n log n) 一类的。dp 数组在每个询问里都要重新算一遍因为 k 变了合法的转移窗口也变了dp 值自然不同。所以这道题的目标很明确把单个询问从 O(nk) 优化到 O(n)其中最关键的就是如何快速从窗口里挑出最优的转移点。2. 从暴力DP到单调队列优化的推导过程2.1 先写出能拿分的 O(nk) 转移方程不管三七二十一先写一个最直观的 DP。定义 dp[i] 表示小鸟从第 1 棵树跳到第 i 棵树的最小疲劳值。初始状态 dp[1] 0因为起点不需要花费。转移的时候枚举 i 前面的合法起跳点 jfor (int i 2; i n; i) { dp[i] INF; for (int j max(1, i - k); j i; j) { int cost (d[j] d[i]) ? 1 : 0; dp[i] min(dp[i], dp[j] cost); } }这个代码思路完全正确问题是慢。一旦 k 很大内层枚举接近 O(n)整体 O(n^2)。在信奥比赛里这种暴力写法只能用来对拍或者拿部分分不能用来 AC。2.2 为什么代价只有 0 和 1 时单调队列能派上用场单调队列优化的前提是窗口左界随 i 单调移动并且候选集合本身有一个明确的优劣顺序。这道题两个条件都满足。窗口左界是 i-k随着 i 增大左界只会不断向右移动不会往左退回来。这正好符合滑动窗口的性质。候选点的优劣顺序才是重点。如果我们手里有两个候选起跳点 a 和 b在遇到同一个目标 i 时怎么判断哪个一定不差先看 dp 值。如果 dp[a] 比 dp[b] 小比如 dp[a] dp[b] - 1那么无论跳到 i 的代价是多少a 的整体结果都不会超过 b。因为额外的 cost 最多只能差 1dp[a] cost(a, i) dp[b] - 1 1 dp[b] dp[b] cost(b, i)所以 dp 越小的起跳点越优。那如果 dp[a] 和 dp[b] 一样呢这时候就要看高度了。因为 cost 取决于 d[i] 和起跳点高度的关系。分三种情况讨论如果目标 i 的高度高于两棵树那么从谁跳过去都要消耗 1平手如果目标 i 的高度介于两棵树之间那么从较高的树跳过去不消耗从较低的树跳过去消耗 1高树更优如果目标 i 的高度低于两棵树那么从谁跳过去都不消耗平手。结论是dp 值相同的时候起跳点高度越高越优至少不会更差。再进一步如果 dp 相同、高度也相同那么下标更大更靠右的起跳点更好因为它更晚从窗口里过期能覆盖更多未来的位置。所以候选点的优先级可以排序为dp 值小优先dp 值相同高度大优先dp 和高度都相同下标大优先。这个结论是整个单调队列实现的核心一定不能想当然。很多人写到这里会只按 dp 排序或者只按高度排序都是错的。2.3 所谓“更优”到底能不能严格覆盖所有情况刚才证明了 dp 小的起跳点不差但这里有个容易被忽略的点如果 dp 只差 1高度差很多会不会出现低 dp 但高度也低的点被高 dp 但高度极高的点反超举个例子dp[a] 5d[a] 1dp[b] 6d[b] 100。假设目标 i 高度是 50。从 a 跳到 id[i] d[a]cost 为 1总疲劳 6从 b 跳到 id[i] d[b]cost 为 0总疲劳 6。两者平手a 并没有输。再假设目标高度是 200从 a 跳到 i 总疲劳 6从 b 跳到 i 总疲劳 7a 胜目标高度是 0从 a 跳到 i 总疲劳 5从 b 跳到 i 总疲劳 6a 胜。因为 cost 是 0 或 1差值最多是 1所以只要 dp[a] dp[b] - 1a 永远不劣。这里不需要额外比较高度。同理dp 相同的时候高度大的也永远不劣。所以这两条规则合起来就给出了一个稳定可靠的“支配关系”如果候选 b 被新的候选 i 支配即 dp[i] dp[b]或者 dp[i] dp[b] 且 d[i] d[b]那么 b 就是废物可以弹出队列。3. 单调队列维护候选集合的细节3.1 队列里存什么直接存下标最省事很多人第一次写单调队列会想存一个 pair 把 dp 和高度都存进去其实没必要。队列里存下标就够了需要比较的时候直接用 dp[q[tail-1]] 和 d[q[tail-1]]既省空间又少一层封装。数组长度开到 n5 就行因为每个元素最多入队一次、出队一次。手写一个 int 队列比 std::deque 更快也能避免 deque 的边界问题。3.2 队头过期窗口左界是 i-k每次计算 dp[i] 之前要先把队头所有“太老”的下标弹出。合法起跳点必须大于等于 i-k所以判断条件是while (head tail q[head] i - k) head;这里用小于号而不是小于等于是因为下标等于 i-k 是合法的它可以作为当前的转移点。比如 k2从 i-2 跳到 i 正好跳了 2 棵合法。所以如果 q[head] i-k不能弹出。很多人会把这个细节写错导致结果偏大或偏小。最简单的方式是画一条数轴把窗口左界标出来再把自己写的判断条件代进去验证一下。3.3 新元素入队时的队尾淘汰逻辑这是整道题最容易写错的地方。处理完 i 的 dp 值之后要把 i 自己加入队列作为后面位置的候选起跳点。入队之前需要把队尾所有“不优于 i”的元素弹掉。比较规则用前面推导的支配关系假设队尾元素是 b新元素是 i。如果下面两个条件满足任意一个b 就被 i 支配可以弹出dp[b] dp[i]dp[b] dp[i] 且 d[b] d[i]。注意第二个条件里的等号非常重要。当 dp 相同、高度也相同i 因为下标更大在窗口里存活时间更长所以 b 不可能比 i 更优。这里漏掉等号会让队列里出现两个完全等价的候选过期的优先级会乱掉。弹出过程是一个循环不是只弹一次因为可能连续多个队尾元素都是废的while (head tail) { int b q[tail - 1]; if (dp[b] dp[i] || (dp[b] dp[i] d[b] d[i])) { --tail; } else { break; } } q[tail] i;这里建议在写完循环后自己模拟一遍小数据把队列里每个下标的 dp 和高度写出来看看是否满足优先级顺序。3.4 取队头计算 dp 值当队列里的元素都满足优先级顺序后队头就是当前窗口内最优的转移点。计算方式int j q[head]; dp[i] dp[j] (d[j] d[i]);注意这里如果 d[j] d[i]说明跳到更高的树疲劳加 1。如果你的题面描述和我记反了只需要把比较符号改一下单调队列的框架不用动。整个过程中队列的更新顺序是先弹过期队头再计算 dp[i]最后加入 i。顺序不能反。如果先加入 i 再计算 dp[i]就可能出现从 i 自己转移的情况显然错误。4. C实现完整代码与读入优化4.1 为什么我选择手写数组队列而不是 std::deque很多教程喜欢用 std::deque因为代码短。但这道题 n 是 1e6每个询问都会把队列用一遍std::deque 在频繁 push_back 和 pop_back 的时候也会有一些额外开销。手写数组队列只需要一个 int 数组和两个头尾下标内存连续、访问快而且在信奥比赛里这是很常用的基本功。数组长度不需要动态扩容直接开 n5因为每个元素最多入队一次。用 head 和 tail 两个变量控制区间 [head, tail) 里的元素head 表示队头下标tail 表示队尾下一个位置。这个半开区间写起来很顺手不容易越界。4.2 完整 AC 代码下面给出完整的 C 实现。代码里用 scanf 和 printf大多数评测机上已经足够。如果你所在的 OJ 输入非常大可以自己加一个快读但这道题用标准 IO 通常不会成为瓶颈。#include bits/stdc.h using namespace std; const int MAXN 1000000 5; int d[MAXN]; int dp[MAXN]; int q[MAXN]; int main() { int n; scanf(%d, n); for (int i 1; i n; i) { scanf(%d, d[i]); } int Q; scanf(%d, Q); while (Q--) { int k; scanf(%d, k); int head 0, tail 0; q[tail] 1; dp[1] 0; for (int i 2; i n; i) { // 1. 弹出窗口外的过期下标 while (head tail q[head] i - k) { head; } // 2. 用队头最优候选转移 int j q[head]; dp[i] dp[j] (d[j] d[i]); // 3. 把 i 加入队列先弹出队尾所有不优于 i 的元素 while (head tail) { int b q[tail - 1]; if (dp[b] dp[i] || (dp[b] dp[i] d[b] d[i])) { --tail; } else { break; } } q[tail] i; } printf(%d\n, dp[n]); } return 0; }代码很短但每一步都有讲究。注释里已经标清楚了三个步骤的顺序第一次写的时候最好照着这个结构来不要自己随便调整。4.3 多组询问能不能复用 dp 数组这道题有 q 次询问每次给一个不同的 k所以 dp 值必须重新算。为什么不能一次性把所有 k 的答案都算出来因为转移窗口完全取决于 kdp 的每个状态都依赖窗口范围k 不同最优转移点完全不同。而且 q 只有 25每个询问重新跑一遍 O(n)总复杂度 O(qn)在 1e6 的数据量下是可行的。如果你发现某些询问里的 k 重复出现可以做一个简单的缓存k 相同就直接输出上一次的答案能省一点时间。但这不是必须的属于锦上添花。5. 实际提交中的踩坑与验证5.1 最容易犯的错误队尾淘汰条件漏掉等号我第一版代码写的是if (dp[b] dp[i] || (dp[b] dp[i] d[b] d[i])) --tail;看起来没问题实际在高度相等的时候会出错。假设两个候选 dp 相同、高度也相同本来新的 i 一定不比 b 差可以放心把 b 弹掉。但我漏了等号b 被保留了。后面窗口右移时b 会更早过期如果队头正好是 b就会导致转移到错误的最优解答案变大。这个坑很难用小样例一眼看出来因为很多数据不会触发高度完全相等的情况。建议在写条件时直接背下这个规则dp 相等时高度大于等于就可以弹。这和我前面推导的“高度相同下标新者优”是一致的。5.2 先维护窗口再转移顺序不能乱还有一个经典错误是循环里先算了 dp[i]再去处理队头过期。比如这么写for (int i 2; i n; i) { int j q[head]; dp[i] dp[j] (d[j] d[i]); while (head tail q[head] i - k) head; ... }看起来只差两行顺序但如果你先取队头此时的队头可能已经不满足 j i-k 了用了一个早就滑出窗口的转移点答案自然错。正确顺序永远是弹出过期队头用当前队头算 dp[i]把 i 插入队列同时淘汰队尾。记忆方法在滑动窗口里永远是“先删旧的再用新的”。5.3 用暴力对拍确认正确性这道题代码短但比较规则容易写错强烈建议写一个暴力 DP 做对拍。暴力枚举所有合法 j复杂度 O(nk)只适合小数据。生成随机 n、随机高度数组、随机 k然后对比暴力结果和单调队列优化结果跑几百组全对才能放心提交。对拍代码的思路大概是// 暴力 DPn 和 k 都很小 vectorint bforce(int n, int k, vectorint d) { vectorint dp(n 1, INF); dp[1] 0; for (int i 2; i n; i) { for (int j max(1, i - k); j i; j) { dp[i] min(dp[i], dp[j] (d[j] d[i])); } } return dp; }然后生成数据分别跑两个版本比较 dp[n] 是否相等。我实际对拍时发现漏等号的那版在随机数据里大概跑几十组才会出错所以不要觉得小数据没问题就万事大吉。5.4 其他边界情况如果 k 非常大比如 k n那么窗口左界始终是 1所有位置都可以从第 1 棵树直接考虑单调队列里不会有过期元素。这个情况理论上不会出错但值得单独测一下。如果 n 1那么小鸟已经在终点答案应该是 0。我的代码里循环 for (int i 2; i n; i) 不会执行直接输出 dp[1] 0正确。如果 d 数组高度都是一样的那么每次跳跃代价都是 1答案应该等于从 1 跳到 n 需要的最少步数也就是 ceil((n-1)/k)。用单调队列跑出来也应该得到这个值这是一个很好的 sanity check。6. 这类“有限跳跃0/1代价”DP的通用套路6.1 怎么一眼识别单调队列优化以后做题时如果看到这个形式的转移dp[i] min(dp[j] w(j, i))其中 j 的范围是 [i-k, i-1]并且窗口左界随着 i 增大单调右移同时代价 w 只与 dp[j] 和某个可比较的属性有关那么大概率可以用单调队列。Little Bird 的特殊之处在于 w(j, i) 是 0 或 1而且由高度大小关系决定所以候选点之间可以建立“支配关系”。如果 w 是一个很大的值比如每次跳跃的代价是两个点坐标差的绝对值那么单调队列就不一定适用可能需要用斜率优化或数据结构优化。6.2 和 P1725 琪露诺、P3957 跳房子的对比在洛谷的 DP 优化题单里P1725 琪露诺和这道题非常像也是每个点可以往后跳一段距离问最小花费。那题的花费和当前高度无关只跟落点有关所以单调队列维护 dp[j] 的最小值就行不需要额外比较高度属性写起来更简单。P3957 跳房子要复杂一些它需要二分答案金币数再结合单调队列 DP 判断能否达到目标分数。因为花在二分上DP 里的转移窗口会动态变化但每次 check 的本质还是单调队列这也是信奥里一种很常见的组合二分答案 DP 验证 单调队列优化。做这些题的时候建议放在一起刷你能明显看出套路滑动窗口、单调队列、候选点优先级。Little Bird 恰好是把“候选点优先级”这个点藏得比较深所以值得单独拎出来总结。6.3 一点刷题心得我刷信奥题打卡已经到第 2740 天最大的感受是代码短的题不代表简单P3572 就是一个很好的例子。它真正的难点不在 DP 方程而在单调队列里那个“dp 相同比高度高度相同比新鲜度”的排序规则。如果只背模板遇到这种变体就会懵。建议你把这个题的完整推导过程抄下来或者用自己的话写一遍然后不看任何代码从零敲一遍再对拍验证。只有亲手踩过一次漏等号的坑才能真正记住。最后再分享一个调试小技巧如果你发现答案偏大优先检查是否用了过期的队头如果答案偏小优先检查队尾淘汰条件是不是把不该弹的弹掉了。这两个方向基本能覆盖这道题 90% 的 bug。