NY OJ 1176 免費餡餅 - 動態規劃逆向遞推完整解析

問題重述

Gameboy 站在 0~10 共 11 個位置的線上，初始位置 5。每秒只能移動 ≤1 格（左、右、原地）。第 t 秒位置 x 掉落餡餅（同一時刻同位置可多個）。求最多能接住多少個餡餅。n, t ≤ 100,000。

狀態定義與遞推

關鍵洞察：從最後一秒 逆向遞推 到第 0 秒。
dp[t][x] = 從第 t 秒位置 x 開始，到結束能接的最大餡餅數。
轉移：dp[t-1][x] = pie[t-1][x] + max(dp[t][x-1], dp[t][x], dp[t][x+1])
邊界：x=0 只能來自 x=0,1；x=10 只能來自 x=9,10。
答案：dp[0][5]（初始位置 5，為方便下標從 1 開始，實際用 dp[0][6]）。

優化：滾動數組 + 時間壓縮

• 只需 dp[2][12] 兩行滾動，空間 O(1)。
• 最大時間 Tmax 由輸入決定，僅遞推到 Tmax，而非固定 100,000。
• 用 scanf 讀入，避免 cin 超時。

完整代碼 (C++)

#include 
#include 
#include 
using namespace std;

int dp[2][12];      // 滾動數組：當前行、下一行
int pie[100001][12]; // pie[t][x] 第 t 秒位置 x 的餡餅數

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        memset(pie, 0, sizeof(pie));
        int Tmax = 0;
        for (int i = 0; i < n; ++i) {
            int x, t; scanf("%d%d", &x, &t);
            ++pie[t][x+1];      // 位置 0~10 → 下標 1~11
            Tmax = max(Tmax, t);
        }
        // 逆向遞推：從 Tmax 遞推到 1
        for (int t = Tmax; t >= 1; --t) {
            int cur = t & 1, nxt = cur ^ 1;
            for (int x = 1; x <= 11; ++x) {
                int best = dp[nxt][x];
                if (x > 1) best = max(best, dp[nxt][x-1]);
                if (x < 11) best = max(best, dp[nxt][x+1]);
                dp[cur][x] = pie[t-1][x] + best; // 注意：pie 索引對齊
            }
        }
        printf("%d\n", dp[1][6]); // 第 0 秒位置 5 → 下標 6
    }
    return 0;
}

複雜度分析

• 時間：O(Tmax × 11) ≤ 1.1×10⁶ 操作，極快。
• 空間：O(100001 × 12) ≈ 4.8 MB（pie 表）+ O(1) dp。

常見錯誤

1. 正向遞推：難以處理「未來可達性」，逆向天然符合決策依賴。
2. 位置下標偏移：題目 0~10，代碼建議 +1 映射到 1~11，避免邊界判斷繁瑣。
3. 同一秒同位置多餡餅：++pie[t][x] 而非賦值。