HDU 1176 免費餡餅 - 逆向動態規劃與狀態壓縮優化

HDU 1176 免費餡餅 - 逆向動態規劃與狀態壓縮優化

題目大意

Gameboy 站在座標 5 位置，餡餅從天上掉落在 0-10 共 11 個位置。每秒移動範圍 ≤ 1 格（左/右/不動）。第 T 秒在位置 x 掉落餡餅（可能多個）。背包無限大。求最多能接住多少餡餅。n < 100000, T < 100000。

核心洞察：逆向 DP 消除邊界判斷

正向 DP 需處理左右邊界（位置 0 不能再左，10 不能再右）。逆向 DP 從最大時刻 maxT 向 0 遞推：

• dp[t][pos] = 從時刻 t 位置 pos 開始，到結束能接的最大餡餅數
• 轉移：dp[t][pos] += max(dp[t+1][pos-1], dp[t+1][pos], dp[t+1][pos+1])（邊界自動處理）
• 答案：dp[0][5]（初始時刻 0，位置 5）

狀態轉移方程詳解

// 內層循環：位置 0 到 10
for (int pos = 0; pos <= 10; pos++) {
    if (pos == 0) 
        dp[t][pos] += max(dp[t+1][0], dp[t+1][1]);
    else if (pos == 10)
        dp[t][pos] += max(dp[t+1][9], dp[t+1][10]);
    else
        dp[t][pos] += max({dp[t+1][pos-1], dp[t+1][pos], dp[t+1][pos+1]});
}

空間優化：滾動數組

只依賴 t+1 時刻，使用兩行滾動：

int dp[2][11];  // 當前行、下一行
int cur = 0, nxt = 1;
for (int t = maxT - 1; t >= 0; t--) {
    for (int pos = 0; pos <= 10; pos++) {
        // 計算 dp[cur][pos] 基於 dp[nxt][...]
    }
    swap(cur, nxt);
}
答案 = dp[cur][5];  // 最後一次 swap 後 cur 指向 t=0

完整 AC 代碼（優化 IO）

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

const int MAXT = 100000 + 5;
int dp[MAXT][11];  // 靜態數組足夠快，無需滾動

int main() {
    int n, x, T;
    while (scanf("%d", &n) == 1 && n) {
        memset(dp, 0, sizeof(dp));
        int maxT = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &x, &T);
            dp[T][x]++;          // 同一時刻同位置可能多個餡餅
            maxT = max(maxT, T);
        }
        
        // 逆向 DP
        for (int t = maxT - 1; t >= 0; t--) {
            for (int pos = 0; pos <= 10; pos++) {
                if (pos == 0)
                    dp[t][pos] += max(dp[t+1][0], dp[t+1][1]);
                else if (pos == 10)
                    dp[t][pos] += max(dp[t+1][9], dp[t+1][10]);
                else
                    dp[t][pos] += max({dp[t+1][pos-1], dp[t+1][pos], dp[t+1][pos+1]});
            }
        }
        printf("%d\n", dp[0][5]);
    }
    return 0;
}

關鍵點總結

1. 逆向思維：從終點向起點推，天然處理邊界，代碼更簡潔
2. 時刻壓縮：只需記錄有餡餅的時刻，但 maxT ≤ 100000 直接開數組更快
3. 同位置多餡餅：dp[T][x]++ 而非賦值 1
4. IO 必須用 scanf/printf：數據量大，cin/cout 會 TLE
5. 數組大小：dp[100001][11] 約 4.4MB，靜態分配無壓力