HDU 4826 迷宮探險：三狀態動態規劃

題目大意

m×n 矩陣迷宮，從左上角 (1,1) 走到右上角 (1,n)。每步只能上、下、右移動，不能重複訪問格子。格子有正負金幣。求最大獲得金幣數。

狀態定義

關鍵觀察：由於不能向左走且不重複訪問，每列中路徑呈現「單向穿梭」模式。定義 `dp[i][j][k]` 表示到達 (i,j) 且從第 k 種方向進入的最大金幣：

• `k=0`：從上方 (i-1,j) 向下進入
• `k=1`：從下方 (i+1,j) 向上進入
• `k=2`：從左方 (i,j-1) 向右進入

轉移方程

按列從左到右 DP，列內先處理從左進入，再向下、向上傳遞：

// 初始化第一列
for (int i = 1; i <= n; i++) dp[i][1][0] = dp[i][1][1] = dp[i][1][2] = a[i][1];
for (int i = 2; i <= n; i++) dp[i][1][0] = dp[i-1][1][0] + a[i][1];

for (int j = 2; j <= m; j++) {
    // 1. 從左邊進入 (k=2)
    for (int i = 1; i <= n; i++) {
        dp[i][j][2] = max({dp[i][j-1][0], dp[i][j-1][1], dp[i][j-1][2]}) + a[i][j];
    }
    // 2. 向下傳遞 (k=0)
    for (int i = 2; i <= n; i++) {
        dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][2]) + a[i][j];
    }
    // 3. 向上傳遞 (k=1)
    for (int i = n-1; i >= 1; i--) {
        dp[i][j][1] = max(dp[i+1][j][1], dp[i+1][j][2]) + a[i][j];
    }
}
ans = max({dp[1][m][0], dp[1][m][1], dp[1][m][2]});

關鍵點

• 列內順序至關重要：必須先計算 `k=2`（左來），再 `k=0`（上來），最後 `k=1`（下來），保證依賴已計算。
• 初始值設為 `-INF`，避免非法路徑干擾。
• 終點固定為 (1, m)，取三種進入方向最大值。