[USACO04NOV] Apple Catching G

题意

有两棵苹果树，奶牛一开始站在 1 号树下。

接下来一共 T 分钟，每分钟恰好有一棵树掉下一个苹果。奶牛最多只能移动 W 次，每次可以瞬间从一棵树移动到另一棵树。

问最多能接到多少个苹果。

思路

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

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// brute.cpp：小数据暴力搜索，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXT = 35;

int t, w;
int a[MAXT];
int best_ans;

void dfs(int minute_idx, int used_move, int pos, int got) {
    if (minute_idx > t) {
        best_ans = max(best_ans, got);
        return;
    }

    // 这一分钟开始前不移动。
    int add = (pos == a[minute_idx] ? 1 : 0);
    dfs(minute_idx + 1, used_move, pos, got + add);

    // 这一分钟开始前移动到另一棵树。
    if (used_move < w) {
        int new_pos = 3 - pos;
        int add2 = (new_pos == a[minute_idx] ? 1 : 0);
        dfs(minute_idx + 1, used_move + 1, new_pos, got + add2);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t >> w;
    for (int i = 1; i <= t; i++) {
        cin >> a[i];
    }

    best_ans = 0;
    dfs(1, 0, 1, 0);

    cout << best_ans << '\n';
    return 0;
}

暴力想法很自然：每一分钟都决定“移不移动”，然后搜完整棵决策树。

但这样状态会重复很多，因为真正影响后面决策的只有三件事：

当前到了第几分钟
一共用了几次移动
当前站在哪棵树下

继续观察还能再省一个维度。

因为一开始站在 1 号树下，而每移动一次都会在两棵树之间切换，所以：

如果已经移动了偶数次，那么一定站在 1 号树下
如果已经移动了奇数次，那么一定站在 2 号树下

也就是说，当前位置完全由“移动次数的奇偶”决定，不需要单独存。

于是定义：

dp[i][j] 表示前 i 分钟处理完，并且一共移动了 j 次时，最多能接到多少苹果

转移时有两种情况：

DP 转移方程

设 gain(i,j) 表示第 i 分钟、移动 j 次后是否正好站在掉苹果的树下。那么：

dp[i][j]=\max(dp[i-1][j],\ dp[i-1][j-1]) + gain(i,j)

当 j=0 时，只能从 dp[i-1][j] 转移。

这一分钟前不移动，那么来自 dp[i-1][j]
这一分钟前移动一次，那么来自 dp[i-1][j-1]

转移完后，根据 j 的奇偶就能知道这一分钟站在哪棵树下：

j 为偶数，在 1 号树下
j 为奇数，在 2 号树下

如果刚好和这分钟掉苹果的树相同，就把答案加一。

代码

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
52
53
54#include <bits/stdc++.h>
using namespace std;

const int MAXT = 1005;
const int MAXW = 35;
const int NEG_INF = -0x3f3f3f3f;

int t, w;
int a[MAXT];
int dp[MAXT][MAXW];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t >> w;
    for (int i = 1; i <= t; i++) {
        cin >> a[i];
    }

    for (int i = 0; i <= t; i++) {
        for (int j = 0; j <= w; j++) {
            dp[i][j] = NEG_INF;
        }
    }
    dp[0][0] = 0;

    for (int i = 1; i <= t; i++) {
        for (int j = 0; j <= w; j++) {
            // 不在这一分钟前移动。
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);

            // 在这一分钟前从另一棵树移动过来。
            if (j > 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
            }

            // 移动次数的奇偶决定当前位置：
            // 偶数次在 1 号树下，奇数次在 2 号树下。
            int pos = (j % 2 == 0 ? 1 : 2);
            if (pos == a[i]) {
                dp[i][j]++;
            }
        }
    }

    int ans = 0;
    for (int j = 0; j <= w; j++) {
        ans = max(ans, dp[t][j]);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

状态数是 T * W，每个状态只做常数次转移。

时间复杂度 $O(TW)$ ，空间复杂度 $O(TW)$ 。

总结

这题最关键的点不是“会不会接苹果”，而是：

当前位置不必单独记
它由移动次数奇偶唯一决定

抓住这一点后，就是很标准的二维 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。