枚举最后一个不选的断点，把 DP 转移化为窗口最大值并用单调队列维护。
OJ: luogu
题目 ID: P2627
难度:普及+/提高-
标签:动态规划单调队列前缀和
创建: 2026-01-05 10:39
更新: 2026-10-07 12:15
前置题目
后置题目
roj 3157「Fence」 围栏B 第三类转移把独立项 P_i·j 提到 max 外后，决策量化为 f[i-1][m]-P_i·m，正是复用了 A 教的「窗口单调右移、用单调队列维护窗口最值」这一步，只是把枚举末尾连续长度换成枚举工匠段左端。roj 3647跳房子B 的 check 判定层把 A 教的「窗口单调右移就用单调队列维护最大值」直接套到 f_i 的转移窗口上，外面再叠一层对金币数 g 的二分roj 3571道路游戏B 的转移 dp[j]=P_c[j]+max(dp[k]-P_c[k]-cost) 正是 A 教的「常数项 + 窗口最大值、用单调队列维护断点」这一步的直接复用，只是把单条窗口扩成 n 条对角线各配一个队列，并额外叠加了 A 未涉及的对角线前缀和观察。roj 3151环路运输B 的第三步直接复用 A 教的“窗口两端单调右移→单调队列取窗口最大值”，只是把窗口值的下标范围从 i-k 换成 j-Kroj 1603「一本通 5.5 练习 2」绿色通道B 的判定 DP 里『队首出窗后即为窗口最小值的下标』就是 A 教的『窗口极值用单调队列维护断点』那一步（A 取 max、B 取 min），B 只在外面再叠一层二分答案roj 1605「一本通 5.5 练习 4」股票交易B 沿用 A 的拆项套路：把不参与比较的 price·j 提出后，窗口内被最大化的量只与决策下标有关，再用单调队列维护随 j 单向平移的窗口最大值，从单个断点窗口扩到买卖两个窗口。roj 1602「一本通 5.5 练习 1」烽火传递B 正解（main.py 单调队列）把 A 教的「窗口随 i 单调右移、用单调队列维护断点取最值」直接套在自己的 dp[i]=a_i+min(dp[i-m..i-1]) 上，只是把 A 的最大值窗口 [i-k,i]（含 dp[j-1]-S[j]）换成最小值窗口 [i-m,i-1]（纯 dp[j]），并额外叠加相邻选中点建模、尾部豁免与哨兵。luogu U663797疯狂的背包问题(10) - 多重背包问题 IIIB 的 main.cpp 按体积余数分组后把多重背包转移整理成 kw + 窗口内 (g[r+jv]-jw) 最大值，正是 A 教的『转移化成常数项加窗口内 dp[j-1]-S[j] 最大值、用单调队列维护右移窗口取队首』这一步的直接套用，只是窗口从 1D 断点 j 搬到等差数列组内下标 k，并叠加余数分组、g 备份这两个 A 未教的新步骤。luogu P2254[NOI2005] 瑰丽华尔兹A 教的「枚举断点把转移化成 常数 + 窗口内 dp[j-1]-S[j] 最大值，窗口随枚举量单调右移」正是 B 的 move_right/up 等四个函数在做的事：dp[x][y]=y+max(old_dp[x][k]-k) 的窗口最值交给单调队列取队头（B 代码 old_dp[row][q[head]]-q[head]+col），B 只是把 1D 断点窗口按整段时间搬到网格行/列，并加上遇家具清空队列。
题意
有 n 只奶牛排成一排，第 i 只奶牛效率为 e[i]。可以选择一些奶牛获得效率和，但不能选择超过 k 只连续的奶牛。求最大效率和。
思路
一个直接 DP 是：令 dp[i] 表示考虑前 i 只奶牛的最大效率，然后枚举末尾连续选了多少只。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：枚举最后一个不选的位置 j，复杂度 O(nk)，只适合小数据。
const int MAXN = 305;
int n, k;
long long e[MAXN];
long long prefix_sum[MAXN];
long long dp[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> e[i];
prefix_sum[i] = prefix_sum[i - 1] + e[i];
}
for (int i = 1; i <= n; i++) {
long long best = 0;
for (int j = max(0, i - k); j <= i; j++) {
long long left_best = 0;
if (j > 0) {
left_best = dp[j - 1];
}
long long value = left_best + prefix_sum[i] - prefix_sum[j];
if (j == max(0, i - k) || value > best) {
best = value;
}
}
dp[i] = best;
}
cout << dp[n] << '\n';
return 0;
}把“末尾连续选了多少只”换成“最后一个不选的位置 j”更好写。若最后一个不选的位置为 j，那么 j+1..i 全部选中，长度要求 i-j <= k，贡献为：
text
dp[j-1] + S[i] - S[j]其中 S 是前缀和。于是：
text
dp[i] = S[i] + max(dp[j-1] - S[j]) (i-k <= j <= i)对固定的 i，S[i] 是常数，只需要找窗口 [i-k, i] 中 dp[j-1]-S[j] 的最大值。这个窗口随 i 单调右移，因此用单调队列维护断点 j 即可。
注意 j=0 表示前面没有断点，可以从第 1 只开始连续选择。这个初始断点必须先放入队列。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, k;
long long e[MAXN];
long long prefix_sum[MAXN];
long long dp[MAXN]; // dp[i] 表示考虑前 i 只奶牛，合法选择的最大效率。
int que[MAXN]; // 单调队列存断点 j，按 dp[j-1]-prefix_sum[j] 从大到小维护。
long long value_of_break(int j) {
long long left_best = 0;
if (j > 0) {
left_best = dp[j - 1];
}
return left_best - prefix_sum[j];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> e[i];
prefix_sum[i] = prefix_sum[i - 1] + e[i];
}
int head = 1, tail = 1;
que[1] = 0; // j=0 表示前面没有断点，可以从第 1 只开始连续选择。
for (int i = 1; i <= n; i++) {
int j = i;
while (head <= tail && value_of_break(que[tail]) <= value_of_break(j)) {
tail--;
}
tail++;
que[tail] = j;
// 断点 j 必须满足 i-k <= j <= i，保证 j+1..i 连续选择不超过 k 只。
while (head <= tail && que[head] < i - k) {
head++;
}
dp[i] = prefix_sum[i] + value_of_break(que[head]);
}
cout << dp[n] << '\n';
return 0;
}复杂度
时间复杂度
空间复杂度
总结
本题的重点是把“连续不超过 k 个”转成“枚举最后一个不选的位置”。整理出 S[i] + max(dp[j-1]-S[j]) 后，单调队列优化就很自然。
。因此，现在 Farmer John 需要你的帮助，计算 FJ 可以得到的最大效率，并且该方案中没有连续的超过