这段时间在整理信奥刷题笔记打卡系列已经写到第2740题。今天挑出来讲的是洛谷上的 P3572 [POI 2014] PTA-Little Bird。这道题名字看着像是一只在树上跳来跳去的小鸟实际上是一道非常标准的单调队列优化 DP很适合刚学完基础动态规划、想往优化方向进阶的人。题目本身不复杂但藏了不少坑等号要不要算体力消耗、队列里的元素按什么顺序排、多组询问怎么处理这些点如果没想透写出来的 C 代码就会在样例和随机数据之间反复横跳。这篇博文我按自己踩坑的顺序来讲先还原题意再推 DP然后给出完整实现最后把调试经验和易错点一起倒出来。1. 先别急着写代码把题目和背景吃透1.1 题意还原一只小鸟和 k 棵树题目描述得很生活化有一排树每棵树有一个高度小鸟从第一棵树出发想飞到最后一棵树。每次跳跃的距离有限制如果从第 i 棵树起跳它只能落到第 i1、i2、……、ik 棵树中的某一棵上不能越过 k 棵树的距离。树的高度会直接影响小鸟的体力如果落点树的高度不低于当前所在树的高度小鸟就要消耗 1 点体力如果落点树更矮则不消耗体力。现在要给多组询问每组询问给一个 k问从第一棵树飞到最后一棵树的最小体力消耗是多少。这里我统一用 0 到 n-1 的下标来讲写代码时也这样实现。树 i 的可达范围是闭区间 [i1, ik]但要裁剪到 n-1 以内。起点是树 0终点是树 n-1。注意消耗体力的条件是“不低于”也就是 h[j] h[i] 时消耗 1而不是严格大于。这一点题面里通常写得很隐晦很多人第一眼会当成“只有向上跳才消耗”结果在等号数据上直接翻车。数据范围方面n 最大可以到百万级别询问次数 q 不大通常只有两位数这意味着对每个询问单独做一次 O(n) 的扫描是可行的。我后面会把这个数量级详细算一遍。1.2 PTA 和 POI 2014 到底指什么标题里 P3572 是洛谷的题号[POI 2014] 表示这是波兰信息学奥林匹克竞赛 2014 年的题目。POI 全称是 Polish Olympiad in Informatics出题质量在圈内一直很高很多题看似背景轻松实际背后都有完整的算法模型。PTA 这个缩写容易让人想到国内的程序设计能力测试平台但这题里的 PTA 是原题代号来自波兰语“Ptaszek”意思就是“小鸟”英文名也就是 Little Bird。所以看到 PTA 不要被名字带偏它和天梯赛、模式匹配那些 PTA 题目没有任何关系。这类“历史题号 原题代号”的命名在 OI 平台很常见。刷题时如果光看题名觉得莫名其妙就去搜题解里的关键词比如这个题的真正核心是“单调队列 0/1 DP 优化”知道这一点比记住题目的背景故事有用得多。1.3 一个手动推一遍的小例子为了先把状态转移讲清楚我构造一个非常小的数据n 4树高分别是 [5, 2, 4, 6]k 2小鸟从树 0 出发树 0 高度 5。如果直接跳到树 1高度从 5 到 2树 1 更矮体力消耗 0如果跳到树 2高度从 5 到 4更矮消耗也是 0不能跳树 3因为距离 3 k2。最终怎么走消耗最小路径 0 - 1 - 2 - 30-1 消耗 01-2 从 2 到 4 是上升消耗 12-3 从 4 到 6 上升消耗 1总消耗 2。路径 0 - 2 - 30-2 消耗 02-3 从 4 到 6 消耗 1总消耗 1。所以答案是 1。这个例子很小但它暴露了一个关键信息小鸟不是每步都必须跳到最近的树有时候跳得远一点反而省体力。也就是说决策点在于每个树前从哪些候选树转移过来这是一个典型的动态规划最短路结构。2. 朴素 DP 入门为什么 O(nk) 会超时2.1 状态定义与转移方程设 dp[i] 表示从树 0 到达树 i 的最小体力消耗。显然 dp[0] 0。对于 i 1树 i 可能由树 j 转移而来条件是 j 在 i 的跳跃范围里也就是max(0, i - k) j i从 j 跳到 i 的额外代价是h[j] h[i] ? 1 : 0所以朴素转移方程就是dp[i] min(dp[j] (h[j] h[i]))其中 max(0, i-k) j i注意这里的比较写法如果落点高度不低于当前高度就加 1。等号是包含在内的所以代码里写h[j] h[i]。这个细节我后面会反复强调因为它是第一个容易写错的地方。2.2 复杂度账本百万数据为什么必须优化直接按照上面的式子写循环每个 i 都要扫描最多 k 个前驱单次询问的复杂度是 O(nk)。当 n 10^6、k 5 * 10^5 时单次询问就是 5 * 10^11 次运算别说 1 秒一分钟都未必跑得完。就算 k 很小比如 k 100单次询问也有 10^8 次运算再加上多组询问照样可能超时。所以在写任何优化之前先要清楚问题的瓶颈在哪里一是前驱数量太多二是每一棵树的候选范围都在滑动。如果能把每个 i 的候选集中到常数个整个问题就变成 O(n) 了。这也是单调队列这类滑动窗口优化技术出现的根本原因。2.3 从“直接取最小 dp”到“双关键字”看到滑动窗口很多人第一反应是“用单调队列维护 dp[j] 的最小值”。这是对的思路但这里不能直接用因为转移代价里还夹着一个和 h[i] 有关的比较项 h[j] h[i]。普通的滑动窗口假设每个候选的“价值”是固定的可以预处理一个值放入队列但这里的候选价值会随着当前树高度 h[i] 的变化而变化不能简单地把 dp[j] 当成固定权重。打个比方假设你面前有几根柱子每个候选树上站着一个工人他们的“底薪”是 dp[j]但能不能拿到奖金要看你和当前树谁高。底薪低的不一定最终成本低因为当前树高度一变奖金归属就变了。所以我们不能只按 dp[j] 排需要找到一个新的排序规则让任何时刻从队首取出来的候选都是全局最优的。3. 单调队列优化记住“dp 相同选高树”3.1 代价只有 0/1 带来的关键性质这题的特殊之处在于额外代价不是随机的它只有 0 和 1 两种可能。于是可以导出两个非常重要的结论。第一个结论如果 dp[x] dp[y]那么无论当前树高度 h[i] 是多少从 x 转移来的总代价一定不大于从 y 转移来的总代价。原因很简单从 x 转移的代价最多比 dp[x] 多 1而从 y 转移的代价最少等于 dp[y]。由于 dp[x] 和 dp[y] 都是整数且 dp[x] dp[y]一定有 dp[x] 1 dp[y]。所以 x 的最差情况也不会比 y 的最好情况差。这说明“dp 值越小候选越优”的大方向是成立的。第二个结论如果 dp[x] dp[y]这时底薪一样要比的就是高度了。若 h[x] h[y]那么从 x 转移一定不比从 y 转移差。分三种情况看如果当前树高度小于 h[y]那么 h[x] 和 h[y] 都高于当前树两个都不额外消耗扯平如果当前树高度小于 h[x] 但不小于 h[y]那么从 x 转移不消耗从 y 转移消耗 1x 更优如果当前树高度不小于 h[x]那也不小于 h[y]两者都消耗 1又扯平。所以无论 h[i] 是什么更高的候选总是不吃亏。这两个结论合起来就得到一个完整的排序规则候选按 dp 值从小到到大排dp 值相同时按树高从高到低排。这样排出来的队首在任意 h[i] 下都一定是所有候选里最优的那个。3.2 双关键字比较函数的严格定义有了上面的规则就可以写比较函数了。假设队尾元素是 b新来的候选是 a如果 a 更适合留在队列里就把它替换 b。适合替换的条件是dp[a] dp[b] 或者 dp[a] dp[b] h[a] h[b]高度相同时也用 新元素下标更大在未来窗口滑动时会更晚过期所以保留新元素永远不亏。这也是单调队列常见的套路当两个候选完全等价时留下标大的那一个。这个比较函数看起来很简单但它是全题的核心。一定要记住单调队列里不只是按 dp 排dp 相同时高度顺序必须正确。我最早写这道题时只按 dp 排样例能过一到随机数据就挂后来把第二条补上才稳定通过。3.3 单调队列维护过程单调队列里存的是树的下标队列内部按上面说的双关键字规则有序。整个求解过程可以这样描述初始化队列把树 0 放进去dp[0] 0。从 i 1 开始枚举到 n-1先把队列头部所有超出跳跃范围的树删掉。判断条件是que[head] k i表示队首连当前树 i 都够不到。此时队首就是当前窗口内最优的转移来源令 dp[i] dp[队首] (h[队首] h[i])。算完 dp[i] 后把 i 本身放入队列。入队前从队尾开始检查凡是“不如 i 优秀”的旧元素都可以弹出因为它们以后不会再成为最优候选。最后 dp[n-1] 就是答案。这里需要注意必须先算 dp[i] 再把 i 插入队列因为树 i 不能从自己转移。算完 dp[i] 后i 作为下一棵树的候选才需要参与队列维护。这个“先取后插”的顺序一旦搞反当前点就会自己转移到自己答案会错得莫名其妙。3.4 为什么队首一定是全局最优每次计算 dp[i] 之前队列里恰好包含窗口 [i-k, i-1] 中经过筛选的候选。由于队列按“dp 值升序、dp 相同时高度降序”排列队首就是全局范围内的最优候选。我上面已经证明dp 小的候选人一定不会输给 dp 大的候选人dp 一样时高度高的候选人一定不会输给高度低的候选人。所以队首的计算结果就是 dp[i] 的最小值。这种做法的本质是把“候选价值随 h[i] 变化”的问题转化成一个可静态排序的问题。底薪相差至少 1 时最高奖金 1 也无法翻盘底薪完全一样时高度就成了唯一决定因素。4. 用 C 把思路落地4.1 数据结构数组模拟队列在信奥里用std::deque写单调队列当然可以但我更建议用数组模拟。一方面代码可控不会因为 STL 底层分配而引入不必要的常数另一方面数组队列的调试信息非常直观队列区间就是 [head, tail)。这里直接用两个整数 head、tail 表示队列的头尾tail 指向队尾后一个空位有效元素是 [head, tail)。const int MAXN 1000000 5; int h[MAXN]; int dp[MAXN]; int que[MAXN]; bool better(int a, int b) { if (dp[a] ! dp[b]) return dp[a] dp[b]; return h[a] h[b]; }better(a, b)表示“新候选 a 是否可以把队尾 b 挤掉”。如果 a 的 dp 更小或者 dp 相等但 a 的树高更高那就把 b 弹出。4.2 solve 函数主循环每个询问单独调用一次solve(k)k 是本次的可跳距离。核心代码int solve(int k) { int head 0, tail 0; que[tail] 0; dp[0] 0; for (int i 1; i n; i) { while (head tail que[head] k i) head; int best que[head]; dp[i] dp[best] (h[best] h[i]); while (head tail better(i, que[tail - 1])) --tail; que[tail] i; } return dp[n - 1]; }这里que[head] k i表示队首已经超出当前点能到达的范围。因为从队首树跳到 i如果跳数超过 k 就够不到必须弹出。注意是 i还是 i如果que[head] k i表示正好可以跳到 i应该保留。dp[i] dp[best] (h[best] h[i])里的比较运算符一定要和题面一致。我在这里按“落点不低于当前树就消耗 1”来写所以用。4.3 完整可提交代码把输入输出和主函数补全就是一份可以直接提交的版本#include bits/stdc.h using namespace std; const int MAXN 1000000 5; int n, qnum; int h[MAXN]; int dp[MAXN]; int que[MAXN]; inline bool better(int a, int b) { if (dp[a] ! dp[b]) return dp[a] dp[b]; return h[a] h[b]; } int solve(int k) { int head 0, tail 0; que[tail] 0; dp[0] 0; for (int i 1; i n; i) { while (head tail que[head] k i) head; int best que[head]; dp[i] dp[best] (h[best] h[i]); while (head tail better(i, que[tail - 1])) --tail; que[tail] i; } return dp[n - 1]; } int main() { scanf(%d, n); for (int i 0; i n; i) scanf(%d, h[i]); scanf(%d, qnum); while (qnum--) { int k; scanf(%d, k); printf(%d\n, solve(k)); } return 0; }这段代码的核心思路并不复杂但它能跑的规模很大。n 是 10^6q 最多两位数总运算量就落在 10^7 到 10^8 级别C 完全扛得住。数组全部开成全局变量避免在函数内部反复构造大数组。better加inline是为了减少比较函数的调用开销虽然在这个量级下不是必须的但养成习惯没坏处。4.4 复杂度与计算量评估每个询问solve里的 for 循环执行 n-1 次每个元素最多入队一次、出队一次。每一次入队和出队的均摊代价是 O(1)所以单次询问是 O(n)。空间上三个数组都是 n 量级总空间 O(n)。如果有 q 次询问总复杂度是 O(qn)。这正好匹配题目 n 很大、q 很小的数据特点。如果你看到的题目 q 也很大比如上万次那么 O(qn) 就危险了需要换离线分治或者更高级的优化。但至少在这道洛谷 P3572 的标准解法里对每个询问单独跑一遍单调队列 DP 就是官方级别的时间复杂度不需要过度设计。5. 现场排雷我踩过的坑与调试技巧5.1 坑一等号比较写反这是这题最容易犯的错误。我刚开始写的时候觉得“飞到更高的树才消耗体力”顺手就写成了h[best] h[i]结果所有高度相同的跳跃都没有消耗答案在包含等号的数据上全部偏小。其实题面说的是“如果不比当前树低”也就是h[j] h[i]时消耗 1等价于代码里h[best] h[i]。你怎么判断自己有没有写反可以拿我前面那个样例去试树高 [5, 2, 4, 6]k2正确答案是 1。如果写反某些转移会异常地便宜答案很可能变成 0。这个等号问题的通用处理方式是读题时把“不低于”“不少于”“至少和它一样高”这类表述精确翻译成代码。不要凭直觉写严格大于小于。5.2 坑二队列维护顺序错误第二个容易踩坑的地方是先入队当前树再计算 dp[i]。一旦当前树被提前放进队列它在计算 dp[i] 时就会作为候选出现造成“在同一棵树上自跳”答案会变得非常稳定地偏小而且很难一眼发现。正确顺序永远是把当前点算完再把它加入队列。更稳妥的写法是先把过期元素弹出再取队首再计算 dp[i]最后插入 i。这个顺序在代码里是有严格因果关系的dp[i] 必须依赖窗口 [i-k, i-1] 的队首而 i 下一次才会成为别人的前驱。5.3 坑三多组询问互相污染由于 solve 函数会重用 dp 数组如果上一次询问没有把 dp 数组全部覆盖下一个询问就可能读到旧值。好在我上面的代码是从 i1 开始逐个赋值 dp[i]每个询问都会把 dp[1] 到 dp[n-1] 重新填一遍dp[0] 也在开头赋成 0所以没有问题。但如果你稍微改一下循环起点比如从某个非零位置开始或者 dp[0] 没有被重置就可能出现“第一次询问正确第二次询问答案突然变大”的诡异现象。排查方法是每次 solve 开头打印一下 dp[0] 和队列初始状态或者直接把 dp 数组用 0x3f 初始化确保所有节点都被覆盖到。5.4 对拍方法暴力程序五步搞定对于这类 DP 题写一个朴素版本做对拍是最省心的验证方式。暴力版直接按转移方程来int brute(int k) { vectorint f(n, 1e9); f[0] 0; for (int i 1; i n; i) { for (int j max(0, i - k); j i; j) { f[i] min(f[i], f[j] (h[j] h[i])); } } return f[n - 1]; }然后随机生成 n 12、k 随机的数据让暴力版和单调队列版跑相同输入比较输出。随机数据生成时一定要保证高度数列里包含相等的高度否则等号错误根本测不出来。我一般会既生成随机高度也单独构造一些全等、单调递增、单调递减的极值数据这样排查起来更全面。5.5 常见错误速查表错误现象可能原因解决方法答案偏小等号比较写反或当前点提前入队检查h[best] h[i]确保先取队首再入队多次询问答案混乱dp 数组残留旧值队列未清空每次 solve 里重置 head/taildp[0] 重新赋值数组越界队列 head/tail 维护错误所有访问前判断head tail耗时过大使用了 O(nk) 的朴素算法确认用双关键字单调队列优化同一个样例反复错better 函数只按 dp 排序dp 相同时必须按高度排且高度大者优先5.6 关于 IO 和常数的经验n 在百万级别读入只需要 scanf 就够不需要自己写快读。但如果题目时限特别紧可以把better函数里访问的数组改成int类型避免任何多余的类型转换。不要在循环里用endl它会在每次输出时刷新缓冲区多组询问时会影响性能用\n或 printf 就好。还有一个被很多人忽略的点MAXN要留出一点余量比如1000000 5。虽然理论上 n 只到 10^6但队列最多会入队 n 个元素加上初始化时可能先放一个 0数组下标最大是 n-1所以数组长度 n1 以上就安全。多开 5 个纯属保险习惯防止边界数据触发越界。这道题刷完以后我对“代价只有 0/1 时的单调队列优化”有了更深的理解。以前遇到滑动窗口 DP 总是机械地塞 dp 值遇到额外代价就头大现在再看这种问题会先去观察代价的取值范围把“低 dp 高高度”这种组合潜力想清楚再决定队列里该按什么顺序排。这类题的价值不在代码本身而在那个“dp 相同选高树”的关键观察上。如果你也在刷 P3572建议不要只抄代码把两个引理自己在纸上推一遍遇到变体题目会轻松很多。