NOJ 1060 接蘋果：二維動態規劃解法詳解

題目背景

農夫約翰的農場有兩棵蘋果樹（編號 1 和 2），奶牛貝茜無法爬樹摘果，只能在果實掉落時接住。每分鐘兩棵樹中會有一棵掉下一顆蘋果，貝茜站在樹下必能接住。她移動極快（遠小於 1 分鐘），但不想頻繁往返，因此最多只願意移動 W 次（1 ≤ W ≤ 30）。給定 T 分鐘（1 ≤ T ≤ 1000）內每分鐘掉果的樹編號，求貝茜最多能接住多少顆蘋果。初始位置在 1 號樹下。

輸入輸出格式

第一行包含兩個整數 T 和 W。接下來 T 行，每行一個整數（1 或 2），表示該分鐘掉果的樹編號。輸出一個整數，表示最多能接到的蘋果數。

範例

輸入：

7 2
2
1
1
2
2
1
1

輸出： 6

說明：貝茜先在 1 號樹接兩顆，移至 2 號樹接兩顆，再移回 1 號樹接最後兩顆，共接 6 顆，移動 2 次。

動態規劃思路

定義 dp[i][j] 為前 i 分鐘、移動 j 次時能接到的最大蘋果數。狀態轉移考慮第 i 分鐘是否移動：

• 若移動：dp[i][j] = dp[i-1][j-1] + 當前位置是否有蘋果
• 若不移動：dp[i][j] = dp[i-1][j] + 當前位置是否有蘋果

當前位置由移動次數奇偶決定：j 為奇數時在 2 號樹，偶數時在 1 號樹（含初始位置）。

初始化細節

dp[i][0] 表示從不移動，始終在 1 號樹，累計 1 號樹掉落的蘋果數。dp[1][j] 表示僅考慮第 1 分鐘，在樹下移來移去的情況。注意當 W=0 時，移動初始化迴圈不執行，需單獨處理 dp[i][0]。

完整代碼 (C++)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_T = 1010;
const int MAX_W = 35;

int dp[MAX_T][MAX_W];
int apple[MAX_T][3]; // apple[i][j]=1 表示第 i 分鐘 j 號樹有蘋果

int main() {
    int T, W;
    scanf("%d%d", &T, &W);
    for (int i = 1; i <= T; ++i) {
        int t; scanf("%d", &t);
        apple[i][t] = 1;
    }

    // 初始化 dp[1][j]
    for (int j = 1; j <= W; ++j) {
        if (j % 2 == 1) dp[1][j] = apple[1][2];
        else dp[1][j] = apple[1][1];
    }
    // 初始化 dp[i][0] (不移動)
    for (int i = 1; i <= T; ++i) {
        dp[i][0] = dp[i-1][0] + apple[i][1];
    }

    // DP 轉移
    for (int j = 1; j <= W; ++j) {
        for (int i = 2; i <= T; ++i) {
            int curTree = (j % 2 == 1) ? 2 : 1;
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + apple[i][curTree];
        }
    }

    int ans = 0;
    for (int j = 0; j <= W; ++j) ans = max(ans, dp[T][j]);
    printf("%d\n", ans);
    return 0;
}

複雜度分析

時間複雜度 O(T·W)，空間複雜度 O(T·W)，滿足題目限制（T≤1000, W≤30）。