企业官网建设流程全解析

信息学奥赛一本通 1599 的【例 3】修剪草坪，对应的就是洛谷 P2627 [USACO11OPEN] Mowing the Lawn G。这道题我给不同阶段的学生讲过很多遍，几乎每次都会遇到同一个现象：DP 方程看着不难，单调队列优化的代码也能背下来，但自己写的时候总是卡在边界条件上，或者干脆说不清“队列里到底存的什么、为什么能这样优化”。这篇文章就把这道题从题意、状态设计、单调队列原理，到代码边界和常见翻车现场，完整拆一遍。

这道题本身是个经典模型：有 n 头奶牛排成一排，每头有一个效率值，要选一部分奶牛让总效率最大，但限制条件是连续选择的奶牛不能超过 k 头。数据范围 n 最大 10^5，效率值最大 10^9。看到这个范围基本就锁死了思路——要么 O(n log n)，要么 O(n)，而标准做法正是用单调队列把 O(nk) 的区间 DP 优化成 O(n)。如果你在备战提高组，或者刚开始接触“单调队列优化 DP”这个专题，这道题是非常合适的入门样本。它没有太多花哨的变形，但把所有核心细节都占全了。

1. 题目到底在限制什么

1.1 把场景翻译成决策问题

先别急着写代码，把题意彻底吃透。FJ 要修剪草坪，把奶牛当成一排“可选可不选”的工作岗位，每头牛有正效率值。约束不是总数量不能超过 k，而是“连续选择的奶牛数”不能超过 k。换句话说，中间只要隔一头不选，连续计数就重新开始。

拿原题样例来推演：n=5，k=2，效率分别是 1、2、3、4、5。全选显然不行，因为连续 5 头超过了 2。最优解是选第 1、2、4、5 头，即两个连续段 [1,2] 和 [4,5]，总效率 1+2+4+5=12。注意第 3 头被空出来了，它就是一个“断点”。或者也可以选第 2、3 头得 5，再选第 5 头得 5，总共 10，比 12 小。

这里最容易犯的直觉错误是“从大到小贪心选”。比如先选效率最高的 5，然后选 4，它俩相邻没问题；接着想选 3 时发现 3、4、5 连续 3 头超过 k=2，于是放弃 3；再选 2，发现 2、4、5 中 4 和 5 仍连续……这样凑出来是 5+4+1=10，不是最优。贪心之所以不行，是因为某个效率高的奶牛是否该选，取决于它左右两侧的“断点”怎么安排，这是一个全局的、有后效性的结构问题，必须用动态规划来解。

1.2 数据范围给出的强线索

n=10^5，效率值最大 10^9。先把两个结论记在纸上：

• 答案最大可能达到 10^5 × 10^9 = 10^14，int 连边都摸不到，必须用 long long。
• 复杂度必须是 O(n) 或 O(n log n)。如果状态设计成 O(nk) 甚至 O(n^2)，在 n=10^5、k 接近 n 时直接爆炸。

也就是说，我们不光要找对 DP 状态，还得想办法把转移的枚举代价降下来。这也是单调队列登场的原因——它解决的就是“一个滑动窗口里的最大值重复计算”问题。

2. 设计状态：从最后一段连续区间入手

2.1 只看“最后一段”是破题关键

做这类线性 DP，我习惯从最后一个位置反推。假设已经决策到第 i 头牛，那么不管前面怎么选，从 i 往前看，一定存在一个“最后一段连续被选中的区间”，记为 [j+1, i]。这意味着第 j 头牛不选，它是这段连续选择的左边界之前的断点；如果 j=0，表示从第 1 头牛开始就连续选，一直选到 i。

这段区间的总效率可以用前缀和快速求出：sum[i] - sum[j]。前 j-1 头牛的最优决策与后面无关，就是 dp[j-1]。这里特别容易写错成 dp[j]，注意：第 j 头牛已经被当作断点空出来了，能自由决策的只能是前 j-1 头，所以要用 dp[j-1]。

于是核心转移思路就出来了：枚举断点 j 的位置，看哪一段作为最后一段最优。这个 j 不是随便取的，区间长度 i-j 不能超过 k，所以 j 至少要大于等于 i-k。

2.2 状态转移方程的完整形态

设 dp[i] 表示前 i 头牛能获得的最大效率总和，前缀和数组 sum[i]=sum[i-1]+a[i]。

第 i 头牛有两种可能：

• 不选第 i 头：那前 i 头的最优解就是前 i-1 头的最优解，dp[i] = dp[i-1]。
• 选第 i 头：设断点为 j，最后一段是 [j+1, i]，其中 j 的取值范围是 max(0, i-k) 到 i-1。此时 dp[i] = dp[j-1] + sum[i] - sum[j]。

两个情况取 max，就是完整方程：

dp[i] = max( dp[i-1], max{ dp[j-1] + sum[i] - sum[j] | max(0, i-k) <= j <= i-1 } )

边界上要约定 dp[0]=0，dp[-1]=0。为什么要 dp[-1]？因为 j=0 时，dp[j-1]=dp[-1] 表示第 0 头牛（虚拟的断点）之前没有任何牛，收益为 0。

这个方程如果直接做，枚举 j 的代价是 O(k)，总复杂度 O(nk)。n=10^5 时，k 稍大就超时。下一步就是要把那个“枚举 j 取最大值”的过程优化掉。

3. 单调队列优化：把 O(nk) 压缩到 O(n)

3.1 把方程拆出与 j 无关的固定部分

很多同学卡在“不知道单调队列在优化什么”，其实只是没做一步简单的代数变形。看选第 i 头牛时的式子：

dp[j-1] + sum[i] - sum[j]

sum[i] 在枚举 j 的过程中是常量，可以提到外面：

dp[i] = sum[i] + max{ dp[j-1] - sum[j] }

也就是说，对于每个断点 j，我们只关心一个值：

val[j] = dp[j-1] - sum[j]

转移方程变成：

dp[i] = sum[i] + max{ val[j] | max(0, i-k) <= j <= i-1 }

现在问题清晰了：随着 i 从 1 递增到 n，j 的候选范围 [i-k, i-1] 就像一个滑动窗口，右端点每次右移一格，左端点也跟着右移。每到一个新 i，我们想知道这个窗口内 val[j] 的最大值是多少。如果每次都暴力扫一遍窗口，就是 O(k)；如果用一个数据结构能 O(1) 拿到窗口最大值，整体就是 O(n)。单调队列就是干这个的。

这里还有一个很多人忽略的细节：上面只处理了“选第 i 头”的情况，那“不选第 i 头”的 dp[i-1] 怎么办？可以单独写个 max，但更优雅的做法是引入一个“空段”概念：让 j=i 也进入候选范围，此时区间 [i+1, i] 长度是 0，贡献为 dp[i-1]+sum[i]-sum[i]=dp[i-1]。于是两个情况被统一了：

dp[i] = sum[i] + max{ val[j] | max(0, i-k) <= j <= i }

其中 val[i] = dp[i-1] - sum[i] 对应 j=i 的空段。这种做法不仅让代码短，还让思路统一：j 现在允许等于 i，表示“最后一段不存在”，也就是第 i 头不选。

3.2 单调队列里存的是下标，不是值

这是新手最容易踩的坑。单调队列里存的是候选下标 j，而不是 val[j] 本身。原因是：我们不仅需要知道最大值，还要在每次循环时判断队头下标是否已经滑出窗口。如果队里只存值，你根本不知道这个值对应的 j 是什么时候进入窗口的，过期判断无从谈起。

单调性这样维护：队列中的下标，从队头到队尾，对应的 val[j] 严格单调递减。这样一来，队头永远是当前窗口内 val 最大的那个 j。

每次新增一个下标 i，先把它从队尾插入。插入前要做“清理”：把队尾所有 val 不大于 val[i] 的元素全部弹出。为什么“不大于”就能弹？假设有两个候选下标 x < y，并且 val[x] <= val[y]。随着 i 不断增大，窗口左边界不断右移，x 一定比 y 更早过期。在 x 还活着的时候，y 的 val 不比他小；在 x 过期后，y 可能还活着。所以 x 在任何时刻都不可能成为最优解，留着它纯属浪费。

这里还有个容易忽略的点：弹出队的条件写成 val[tail] <= val[i] 还是 val[tail] < val[i]？我建议写成 <=。因为当 val 相等时，保留下标更小的还是更大的？下标更大的 y 过期更晚，在窗口里待得更久，明显更优，所以遇到相等的旧元素直接淘汰。写成 < 虽然结果通常不影响正确性，但队列里会积累一堆相同值的“僵尸下标”，边界判断变麻烦，没必要。

3.3 关键代码顺序：先插入，再取队头

现在把滑动窗口和单调队列拼起来。最让我觉得值得反复讲的是循环里的操作顺序。常见实现是：

初始化队列放入 0 for i = 1 .. n: 计算 val[i] = dp[i-1] - sum[i] 从队尾弹出所有 val <= val[i] 的下标 把 i 插入队尾 从队头弹出所有小于 i-k 的下标 dp[i] = sum[i] + val[队头]

注意这里顺序是“先插入 i，再弹过期队头，再计算 dp[i]”。为什么不是先算 dp[i] 再插入？因为我们的 dp[i] 用了“空段”技巧，j 是可以等于 i 的。先插入下标 i，保证计算 dp[i] 时候选窗口是 [i-k, i]，包含了第 i 头不选的情况。如果先算 dp[i] 再插入 i，那 j=i 这个空段就漏掉了，dp[i] 结果会比正确答案小。很多同学的代码就差这一步顺序，样例都过不了。

再强调一点：插入下标 i 时，val[i] 需要用到 dp[i-1]，而 dp[i-1] 是上一轮循环已经算好的。所以代码的顺序是完全自洽的。初始化队列时放入下标 0，对应的 val[0] 怎么来的？val[0] = dp[-1] - sum[0] = 0。这里 dp[-1] 要手动当成 0 处理，不能写成 dp[0]，否则 i=1 时侯选窗口会被污染。

4. 完整代码与逐行拆解

4.1 C++ 参考实现

下面这版代码我自认为是比较清爽的写法，符合上面的推导，注释也够细：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100005; ll a[MAXN], sum[MAXN]; ll dp[MAXN]; // dp[i]: 前 i 头牛的最大总效率 ll val[MAXN]; // val[i] = dp[i-1] - sum[i]，作为断点 i 的候选值 int q[MAXN]; // 手写队列，存下标 int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); sum[i] = sum[i - 1] + a[i]; } int head = 0, tail = 0; // 初始放入断点 j = 0，对应 val[0] = dp[-1] - sum[0] = 0 val[0] = 0; q[tail++] = 0; for (int i = 1; i <= n; i++) { // 计算当前下标作为断点时的候选值 val[i] = dp[i - 1] - sum[i]; // 维护单调性：队尾所有 val <= val[i] 的都没用了，弹出 while (head < tail && val[q[tail - 1]] <= val[i]) { tail--; } q[tail++] = i; // 弹出过期下标：断点 j 必须满足 j >= i - k while (head < tail && q[head] < i - k) { head++; } // 队头就是当前窗口内 val 最大的断点 int j = q[head]; dp[i] = sum[i] + val[j]; } printf("%lld\n", dp[n]); return 0; }

4.2 几个容易讲不清的细节

第一，val[0] 为什么是 0。回到定义，val[j]=dp[j-1]-sum[j]。当 j=0 时，dp[-1] 这个下标不存在，但它的意义是“断点之前没有任何牛”，收益当然是 0。sum[0]=0，所以 val[0]=0。这行看起来不起眼，删掉它整个代码就会在 i=1 时报错或者答案出错，因为队列空了，取队头会拿到脏数据。

第二，为什么处理完队头过期之后才能取 j 算 dp[i]。窗口下界是 i-k。如果队头下标小于 i-k，说明这个断点会导致最后一段连续区间长度超过 k，是非法的。必须先把这些下标扔出窗口。注意这里判断用的是严格小于，也就是说 q[head] == i-k 是保留的——区间长度正好是 k，合法。

第三，dp[i] 计算用的 j 是队头下标，而 val[j] 用的是当前循环开始前就算好的值。这个顺序不能乱。如果是自己写，我建议先手动模拟一遍样例，确认每一步淘汰了谁、保留了什么，再对着代码看，基本就不会写错了。

4.3 另一种等价写法：显式处理不选的情况

有的题解会把 dp[i-1] 单独拿出来比较，队列窗口中只放 [i-k, i-1] 的断点，即“先查队头、再插入 i”。它的核心是：

dp[i] = max(dp[i - 1], sum[i] + val[q[head]]); // 再算 val[i]、插入队列

这种思路更“诚实”，直接对应第 2.2 节的方程，只是每次要多写一个 max。两种写法等价，本质都是通过 val[j]=dp[j-1]-sum[j] 把断点的贡献统一起来。我个人推荐“空段”写法，因为它能把“不选第 i 头”也纳入同一个框架，后面遇到更复杂的变体时统一性更好。但如果你觉得“先插入”的顺序容易记混，那就用显式 max 的版本，至少思路直白，不容易写出“先插入后取队头却忘了加 max”的 bug。

5. 常见错误与排查实录

5.1 四个高频翻车点

第一个，也是最常见的：所有数值类型都是 int。n=10^5，效率 10^9，前缀和轻轻松松破 10^9，总答案能到 10^14。int 根本装不下，最终答案会变成负数或者莫名其妙的小数。排查方法很简单：把样例往大了造，比如 n=100000、k=1、每个 a[i]=1000000000，看输出是不是 10^14 这个量级。

第二个：val 数组的初始化不对。很多人把 val[0] 漏了，或者错误地让 val[0] = dp[0] - sum[0]。前 1 头牛时队列里可能只有下标 0，val[0] 错的话 dp[1] 就错了，而且会一路传染到最后。建议每次写完检查一下 i=1 和 i=2 这两个最小情况的手算结果。

第三个：过期判断写成了 q[head] <= i - k。这是把“窗口左边界”和“允许的最左侧断点”搞混了。要求最后一段长度不超过 k，也就是 j >= i-k。如果 q[head]==i-k，区间长度正好是 k，完全合法，不应该弹出。写成 <= 就会多弹一个合法候选，结果偏小。

第四个：队尾弹出时用 < 而不是 <=。这个不影响正确性，但会让队列里堆积多个 val 相等的旧下标，拖慢速度，也让调试时队列内容变得难读。还是那句话，相等时保新不保旧。

5.2 自己验证正确性的三板斧

算法题改完代码，别急着交，先在本地做三件事。

第一，手推样例。上面那个 1 2 3 4 5、k=2 的样例，把所有中间数组列出来。我模拟一遍关键步骤：i=3 时窗口是 [1,3]，val[1]=dp[0]-sum[1]=0-1=-1，dp[3]=sum[3]+(-1)=5，对应选第 2、3 头；i=5 时窗口是 [3,5]，最优点是断点 j=3，val[3]=dp[2]-sum[3]=3-6=-3，dp[5]=15-3=12。如果你手推的这几个关键值能对上了，代码大概率没问题。

第二，暴力对拍。写一个 O(nk) 的暴力 DP 和单调队列版跑随机小数据，n 取 10 以内，k 随机，a[i] 随机（包括偶尔出现的小负数，如果题目允许的话），对比输出。对拍能查出几乎所有边界问题。

第三，极限数据压测。n=100000，k 分别取 1、2、99999、100000，全填最大值，看会不会溢出、会不会超时。k=1 时答案应该是所有正效率之和；k>=n 时应该全选，这两个特殊值都是很好的回归测试用例。

6. 同类题与套路迁移

6.1 一个模型，多张皮

这道题的模型非常泛化：“长度为 L 的滑动窗口内取某种最大值，配合线性 DP”。随便举几个例子：

• 洛谷 P2034 选择数字：几乎就是这道题换了个背景，连数据范围都差不多。
• P1725 琪露诺：从 i 可以跳到 [i+L, i+R]，用单调队列维护 dp[i-L] 到 dp[i-R] 的最大值，思路同源。
• P2569 股票交易：买入卖出的状态机加上滑动窗口，同样用单调队列优化，是这道题的进阶版。
• 一本通里的“烽火台传递”也是同一类：每 m 个里至少选一个，最小化代价，转移方程里的“窗口最小值”用单调队列维护。

碰到这类题，我建议先别急着套模板，而是按部就班做四步：写出朴素 O(nk) 的 DP；把与 j 无关的项从 max 中提出来；观察 j 的取值范围是否随着 i 单调滑动；用单调队列存下标维护窗口最值。这套流程熟练以后，单调队列就不再是玄学，而是一种条件反射。

6.2 学这道题真正要带走的能力

回到开头说的那个现象：很多同学能把这道题的代码背下来，但换个马甲就不会了，原因就是没有理解“队列里的每个下标到底代表什么”。在这道题里，每个 j 代表一个断点，也就是“第 j 头牛不选，后面接一段连续选择的牛”。窗口滑动是因为断点的可取范围随着 i 移动，单调性则来自“旧的不可能比新的更优”这一条铁律。

我个人带学生的经验是，这道题值得三刷。第一遍，对着题解把 AC 代码敲出来；第二遍，不看代码，自己在纸上画出 i=1 到 n 每一步队列的内容和 dp 值；第三遍，改写成显式处理不选情况的写法，再通过一次。三遍下来，单调队列优化 DP 这个专题的地基就算扎实了。这也是我认为这道题被放在“信息学奥赛一本通提高篇”例 3 位置上的原因——它不刁钻，但每一个细节都值得回味。