企业官网建设流程全解析

最近刷题打卡正好轮到第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 最大可以到 1000000，q 最大是 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)，在 n=1e6 时完全不可能通过。即使每个询问单独做，也会爆炸。

再看 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 前面的合法起跳点 j：

for (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 最多只能差 1：

dp[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 相同、高度也相同，那么下标更大（更靠右）的起跳点更好，因为它更晚从窗口里过期，能覆盖更多未来的位置。

所以候选点的优先级可以排序为：

1. dp 值小优先；
2. dp 值相同，高度大优先；
3. dp 和高度都相同，下标大优先。

这个结论是整个单调队列实现的核心，一定不能想当然。很多人写到这里会只按 dp 排序，或者只按高度排序，都是错的。

2.3 所谓“更优”到底能不能严格覆盖所有情况

刚才证明了 dp 小的起跳点不差，但这里有个容易被忽略的点：如果 dp 只差 1，高度差很多，会不会出现低 dp 但高度也低的点，被高 dp 但高度极高的点反超？

举个例子，dp[a] = 5，d[a] = 1；dp[b] = 6，d[b] = 100。假设目标 i 高度是 50。从 a 跳到 i：d[i] >= d[a]，cost 为 1，总疲劳 6；从 b 跳到 i：d[i] < d[b]，cost 为 0，总疲劳 6。两者平手，a 并没有输。

再假设目标高度是 200，从 a 跳到 i 总疲劳 6，从 b 跳到 i 总疲劳 7，a 胜；目标高度是 0，从 a 跳到 i 总疲劳 5，从 b 跳到 i 总疲劳 6，a 胜。

因为 cost 是 0 或 1，差值最多是 1，所以只要 dp[a] <= dp[b] - 1，a 永远不劣。这里不需要额外比较高度。同理，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]]，既省空间又少一层封装。

数组长度开到 n+5 就行，因为每个元素最多入队一次、出队一次。手写一个 int 队列比 std::deque 更快，也能避免 deque 的边界问题。

3.2 队头过期：窗口左界是 i-k

每次计算 dp[i] 之前，要先把队头所有“太老”的下标弹出。合法起跳点必须大于等于 i-k，所以判断条件是：

while (head < tail && q[head] < i - k) ++head;

这里用小于号而不是小于等于，是因为下标等于 i-k 是合法的，它可以作为当前的转移点。比如 k=2，从 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 数组和两个头尾下标，内存连续、访问快，而且在信奥比赛里这是很常用的基本功。

数组长度不需要动态扩容，直接开 n+5，因为每个元素最多入队一次。用 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 的答案都算出来？因为转移窗口完全取决于 k，dp 的每个状态都依赖窗口范围，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 了，用了一个早就滑出窗口的转移点，答案自然错。

正确顺序永远是：

1. 弹出过期队头；
2. 用当前队头算 dp[i]；
3. 把 i 插入队列，同时淘汰队尾。

记忆方法：在滑动窗口里，永远是“先删旧的，再用新的”。

5.3 用暴力对拍确认正确性

这道题代码短，但比较规则容易写错，强烈建议写一个暴力 DP 做对拍。暴力枚举所有合法 j，复杂度 O(nk)，只适合小数据。生成随机 n、随机高度数组、随机 k，然后对比暴力结果和单调队列优化结果，跑几百组，全对才能放心提交。

对拍代码的思路大概是：

// 暴力 DP，n 和 k 都很小 vector<int> bforce(int n, int k, vector<int>& d) { vector<int> 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。