形式化题目

给定长度为 $N$ 的非负整数序列 $E_1, E_2, \dots, E_N$ 和非负整数 $K$。选出一个下标子集，要求被选中的下标中任意连续一段的长度不超过 $K$，求选中元素之和的最大值（可以一个都不选，此时和为 0）。

样例：$N=5,\ K=2,\ E=(1,2,3,4,5)$。跳过奶牛 3、选 $\{1,2,4,5\}$，两段连续长度分别为 2 和 2，均不超过 $K=2$，和为 $1+2+4+5=12$，即样例答案。

正解

思路

1. 朴素转移

记前缀和 $S_i = E_1 + \dots + E_i$，$dp[i]$ 为"前 $i$ 只奶牛能得到的最大效率和"。考虑奶牛 $i$：

• 不选：价值 $dp[i-1]$；
• 选：奶牛 $i$ 必属于一个长度不超过 $K$ 的连续段，设段左侧第一只不选的奶牛是 $j$（$j=0$ 表示从头开始选），则 $i - j \leqslant K$ 且 $0 \leqslant j \leqslant i-1$；奶牛 $j$ 不选时方案完全落在前 $j-1$ 只中，反之亦然，所以前缀 $1..j$ 的最优值恰为 $dp[j-1]$，段内和为 $S_i - S_j$。

于是

直接对每个 $i$ 枚举窗口内的 $j$ 是 $O(NK)$：$N$ 达 $10^5$、$K$ 可与 $N$ 同阶时最坏约 $10^{10}$ 次运算，无法通过——这正是要消除的瓶颈。

2. 拆项：窗口最大值

把转移中与 $i$、$j$ 混在一起的项拆开：

所以每个 $i$ 只需要窗口 $[\max(0,\,i-K),\ i-1]$（下文简写为 $[i-K, i-1]$，下标天然非负）内 $h(j) = dp[j-1] - S_j$ 的最大值：

$j$ 的合法范围是长度为 $K$ 的滑动窗口，每步只右移一格，这正是单调队列的舞台：

• 过期：下标 $< i-K$ 的候选出队；下标逐个右移，每步至多一个过期，从队首弹；
• 入队：算完 $dp[i]$ 后候选 $j=i$ 的值 $h(i) = dp[i-1] - S_i$ 就确定了，从队尾弹出所有不大于它的候选（它们下标更大、值更小，永远轮不到），再入队；
• 查询：队首即窗口内 $h(j)$ 最大的下标，均摊 $O(1)$。

初值：$j=0$ 时 $dp[-1]$ 取 0、$S_0=0$，候选值为 0，入队一次即可。每个下标只入队、出队一次，总复杂度 $O(N)$。循环结束时 $dp[N]$ 就是答案。

3. 样例 DP 表格

下表按 main.py 的状态定义逐步演算样例 $E=(1,2,3,4,5),\ K=2$：窗口列是 $j$ 的合法范围 $[i-K, i-1]$，队首候选是单调队列中 $h(j)=dp[j-1]-S_j$ 最大的下标。

观察三点：$j=0$ 的候选一直占着队首，直到 $i=3$ 才过期（$0 < 3-2$）；每步队首都给出窗口内最大的 $h(j)$；第 5 步 $S_5 + h(3) = 15 - 3 = 12$，对应"选 $1,2,4,5$、跳过奶牛 3"，正是样例答案。窗口右移时旧队首弹出、新候选从队尾入队，队列始终保持 $h$ 递减——这就是单调队列的全部内容。

代码与表列一一对应：window 存 $(j, h(j))$、prefix 是 $S_i$、dp_prev 是 $dp[i-1]$、value 是待入队的 $h(i)$；主循环每步恰好按"过期 → 查询得 $dp[i]$ → 入队"的顺序执行，与表格逐行的推进一致。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 20:53
# update_at: 2026-09-30 20:53

import sys
from collections import deque


def max_efficiency(effs: list[int], k: int) -> int:
    """前缀和 + 单调队列求「不选超过 k 只连续奶牛」的最大效率和。

    dp[i] = max(dp[i-1], S[i] + max_{i-k <= j <= i-1} (dp[j-1] - S[j]))，
    其中 j 是连续段左侧第一只不选的奶牛（j = 0 表示从头开始选），
    窗口最大值由下标递增、候选值递减的双端队列维护。
    """
    # (下标 j, 候选值 dp[j-1]-S[j])，队首最大；j=0 的候选值是 0 - S[0] = 0
    window: deque[tuple[int, int]] = deque([(0, 0)])
    prefix = 0      # S[i]：前 i 只奶牛的效率和
    dp_prev = 0     # dp[i-1]：前 i-1 只奶牛的答案

    for i, eff in enumerate(effs, 1):
        prefix += eff                                  # S[i] = S[i-1] + E_i
        if window and window[0][0] < i - k:            # 窗口左端 [i-k, i-1] 过期一个下标
            window.popleft()
        # 只有 k = 0 时窗口为空（一只都不许选），其余情况 dp[i-1] 必在候选里
        dp_cur = prefix + window[0][1] if window else dp_prev
        dp_cur = max(dp_cur, dp_prev)                  # 第 i 只不选，直接继承

        # 入队候选 j = i：值为 dp[i-1] - S[i]（奶牛 i 不选时，前缀最优值）
        # 保持候选值递减，过期下标靠左端弹出，均摊 O(1)
        value = dp_prev - prefix
        while window and window[-1][1] <= value:
            window.pop()
        window.append((i, value))
        dp_prev = dp_cur

    return dp_prev


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)
    effs = [next(data) for _ in range(n)]
    print(max_efficiency(effs, k))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
 * Author by Rainboylv blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 11:52
 * update_at: 2026-10-05 11:52
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

typedef long long ll;

ll n;
ll k;
ll e[MAXN];   // e[i]：第 i 只奶牛的效率
ll s[MAXN];   // s[i]：前缀和，s[i] = e[1] + ... + e[i]
ll dp[MAXN];  // dp[i]：前 i 只奶牛、无超过 k 只连续被选的最大效率和
ll q[MAXN];   // 单调队列存候选断点 j，队首到队尾下标递增、h 值递减
ll h(int j) { // 候选值 h(j) = dp[j-1] - s[j]，只含 j，用于拆项
    return dp[j - 1] - s[j];
}

// 单调队列优化的一维 DP，求无超过 k 连续被选奶牛的最大效率和。
void solve() {
    s[0] = 0;
    for (ll i = 1; i <= n; i++) s[i] = s[i - 1] + e[i];

    // 先把候选 j=0（从头开始选，dp[-1] 视为 0）入队
    int head = 1, tail = 1; // 队列区间 [head, tail)，head==tail 表示空
    q[tail++] = 0;

    for (ll i = 1; i <= n; i++) {
        // 队首过期：断点 j 必须满足 i - k <= j <= i - 1
        while (head < tail && q[head] < i - k) head++;

        // 选到 i：断点 j=i 时不选任何奶牛，对应 dp[i-1]
        dp[i] = dp[i - 1];
        if (head < tail) {
            ll best = s[i] + h(q[head]);
            if (best > dp[i]) dp[i] = best;
        }

        // 入队候选 j=i，队尾弹出所有 h 值不大于它的候选（下标更大、值更小，永远轮不到）
        ll value = h(i);
        while (head < tail && h(q[tail - 1]) <= value) tail--;
        q[tail++] = i;
    }
    cout << dp[n] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (ll i = 1; i <= n; i++) cin >> e[i];
    solve();
    return 0;
}

复杂度

• 时间复杂度：$O(N)$。读入 $O(N)$；每只奶牛的候选恰好入队、出队各一次，队列操作均摊 $O(1)$，DP 主循环每步 $O(1)$。对比朴素 $O(NK)$ 的最坏 $10^{10}$，降为 $2 \times 10^5$ 量级的常数次运算。
• 空间复杂度：$O(N + K)$。效率数组 $O(N)$（前缀和与 dp 只保留滚动变量），单调队列至多存 $K+1$ 个下标；实测峰值内存 $\leqslant 25$ MB，远低于 128 MB 限制。

总结

• 模型是"选/不选"的一维 DP：转移的关键是把连续段左端点 $j$ 理解为断点（奶牛 $j$ 不选），状态价值取 $dp[j-1]$ 而不是 $dp[j]$——写成 $dp[j]$ 会把左右两段连成超过 $K$ 的长段。
• $dp[j-1] + S_i - S_j$ 拆成"只含 $j$"与"只含 $i$"两部分，是队列优化 DP 的标准动作；此后每个 $i$ 只剩一个滑动窗口最值问题。
• 单调队列保证：下标过期只在队首、劣质候选淘汰只在队尾，每个下标进出各一次，$O(NK)$ 因此变成 $O(N)$。
• 边界：$j=0$ 候选值 0 需显式入队；$K=0$ 时窗口为空，只继承 $dp[i-1]$，答案为 0。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5选子集、连续段长 <= K
`- 线性 DP：dp[i] 按奶牛 i 选/不选分两类
   `- 拆项：dp[j-1]-S_j（只含 j）+ S_i（只含 i）
      `- 单调队列维护窗口 [i-K, i-1] 的最大值
         `- 每个下标进出各一次，O(N) 得到 dp[N]

先看每个节点代表的推理结论：从"断点 j 不选"得到正确的状态价值，从"拆项"得到只与 $j$ 有关的候选函数，从"滑动窗口"得到单调队列。顺着分支检查它如何导向下一步，即正文已证明的关键关系；图不替代样例表格中的逐步演算。