[USACO04NOV] 接苹果(Apple Catching) 题解

思路分析

初始在 $1$ 号树下，因此累计移动偶数次时位于 $1$ 号树下，累计移动奇数次时位于 $2$ 号树下（即移动 $j$ 次后所在树编号为 (j % 2) + 1）。设 dp[t][j] 表示前 $t$ 分钟恰好（或至多）移动 $j$ 次最多接到的苹果数，转移方程为 dp[t][j] = max(dp[t - 1][j], dp[t - 1][j - 1]) + (a[t] == (j % 2) + 1)（注意第 $1$ 分钟前也可以先移动 $1$ 次到 $2$ 号树下）。答案为 $\max_{0 \le j \le W} dp[T][j]$，时间复杂度 $O(TW)$。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

int dp[1005][35];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T, W;
    if (!(cin >> T >> W)) return 0;
    for (int t = 1; t <= T; ++t)
    {
        int tree;
        cin >> tree;
        for (int j = 0; j <= W && j <= t; ++j)
        {
            int bestPrev = dp[t - 1][j];
            if (j > 0 && j - 1 <= t - 1) bestPrev = max(bestPrev, dp[t - 1][j - 1]);
            int curTree = (j % 2) + 1;
            dp[t][j] = bestPrev + (tree == curTree ? 1 : 0);
        }
    }
    int ans = 0;
    for (int j = 0; j <= W && j <= T; ++j) ans = max(ans, dp[T][j]);
    cout << ans << "\n";
    return 0;
}