HDU 3853 LOOPS：概率 DP 計算期望魔法值

題目大意

R×C 迷宮，每格有傳送門：以概率 p0 留在原地，p1 向右，p2 向下。每次傳送消耗 2 魔法。從 (1,1) 到 (R,C) 的期望魔法消耗。R,C ≤ 1000。

DP 狀態與轉移

設 `dp[i][j]` 為從 (i,j) 到終點的期望魔法值。終點 `dp[R][C] = 0`。
轉移方程：

`dp[i][j] = p0 * dp[i][j] + p1 * dp[i][j+1] + p2 * dp[i+1][j] + 2`

移項得：

`dp[i][j] = (p1 * dp[i][j+1] + p2 * dp[i+1][j] + 2) / (1 - p0)`

特殊情況：若 `p0 == 1` (死循環)，`dp[i][j] = 0` (或視為不可達，但題目保證有解)。

計算順序

依賴右方和下方狀態，按 行從下到上，列從右到左 逆序計算。

代碼實現 (C++)

#include 
#include 
const int MAX = 1005;
const double EPS = 1e-10;

double p[3][MAX][MAX];
double dp[MAX][MAX];

int main() {
    int R, C;
    while (scanf("%d%d", &R, &C) == 2) {
        for (int i = 1; i <= R; i++)
            for (int j = 1; j <= C; j++)
                scanf("%lf%lf%lf", &p[0][i][j], &p[1][i][j], &p[2][i][j]);
        
        dp[R][C] = 0;
        for (int i = R; i >= 1; i--) {
            for (int j = C; j >= 1; j--) {
                if (i == R && j == C) continue;
                if (fabs(p[0][i][j] - 1.0) < EPS) {
                    dp[i][j] = 0; // 死循環，期望無限大但題目約束下不會作為答案
                } else {
                    dp[i][j] = (p[1][i][j] * dp[i][j+1] + p[2][i][j] * dp[i+1][j] + 2) / (1.0 - p[0][i][j]);
                }
            }
        }
        printf("%.3f\n", dp[1][1]);
    }
    return 0;
}

關鍵點

• 邊界處理：`dp[i][C+1]` 和 `dp[R+1][j]` 默認 0 (全局數組自動初始化)，對應超出邊界視為終點或無效轉移概率為 0 (題目保證邊界概率合理)。
• 精度：用 `double`，輸出 `%.3f` 四捨五入保留 3 位小數。
• 死循環判斷：`fabs(p0 - 1) < EPS` 避免除零。
• 時間 O(R*C)，空間 O(R*C)，R,C≤1000 完全可行。