[USACO11OPEN] Mowing the Lawn G

题意

有 n 只奶牛排成一排，第 i 只奶牛效率为 e[i]。可以选择一些奶牛获得效率和，但不能选择超过 k 只连续的奶牛。求最大效率和。

思路

一个直接 DP 是：令 dp[i] 表示考虑前 i 只奶牛的最大效率，然后枚举末尾连续选了多少只。

先看一个可以直接验证想法的朴素解：

cpp

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#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

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

其中 S 是前缀和。于是：

text

1dp[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

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#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;
}

复杂度

时间复杂度 $O(n)$ ，每个断点最多入队和出队一次。

空间复杂度 $O(n)$ 。

总结

本题的重点是把“连续不超过 k 个”转成“枚举最后一个不选的位置”。整理出 S[i] + max(dp[j-1]-S[j]) 后，单调队列优化就很自然。

[USACO11OPEN] Mowing the Lawn G

目录

题意

思路

代码

复杂度

总结