HDU 1176 免費餡餅：動態規劃自底向上接餡餅

題目大意

Gameboy 在位置 0~10 的線性路徑上移動，初始位置 5。每秒移動 ≤1 格。餡餅在時刻 T 掉落在位置 X。求最多能接住多少個餡餅。

DP 狀態與轉移

dp[t][x]：時刻 t 站在位置 x 能接到的最大餡餅數。
轉移：dp[t][x] = max(dp[t-1][x-1], dp[t-1][x], dp[t-1][x+1]) + pie[t][x]。
邊界 x=0 只能從 0,1 轉移；x=10 只能從 9,10。
時刻最大值 T_max 由輸入決定。自底向上（從 T_max 遞推到 0）或自頂向下均可。答案為 max(dp[0][4], dp[0][5], dp[0][6])（首秒只能到達 4,5,6）。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXT = 100005;
int pie[MAXT][11];
int dp[MAXT][11];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n, n) {
        memset(pie, 0, sizeof(pie));
        int Tmax = 0;
        for (int i=0;i> x >> t;
            pie[t-1][x]++; // 時刻 1 對應索引 0
            Tmax = max(Tmax, t);
        }
        // 初始化最後一層
        for (int x=0;x<=10;++x) dp[Tmax-1][x] = pie[Tmax-1][x];
        // 自底向上
        for (int t=Tmax-2; t>=0; --t) {
            for (int x=1; x<=9; ++x)
                dp[t][x] = max({dp[t+1][x-1], dp[t+1][x], dp[t+1][x+1]}) + pie[t][x];
            dp[t][0] = max(dp[t+1][0], dp[t+1][1]) + pie[t][0];
            dp[t][10] = max(dp[t+1][9], dp[t+1][10]) + pie[t][10];
        }
        int ans = max({dp[0][4], dp[0][5], dp[0][6]});
        cout << ans << '\n';
    }
    return 0;
}

關鍵點

• 時刻從 1 開始，數組索引從 0 開始，注意 t-1。
• 同一時刻同一位置可能掉多個餡餅，用 ++ 累加。
• 自底向上遞推避免邊界條件複雜，需先初始化最後一層。