HDU 3853：向下向右找出口 (期望 DP)

問題描述

n×m 網格，從 (1,1) 走到 (n,n)（題目實為 (n,m)）。每步可向右、向下、或不動，概率分別為 p2, p3, p1（p1+p2+p3=1）。每移動一步（右/下）消耗 2 魔力，不動不消耗。求到達終點期望魔力消耗。

期望 DP 方程

設 dp[i][j] 為從 (i,j) 到終點的期望魔力。終點 dp[n][m] = 0。對於其他格子：

dp[i][j] = p1 * dp[i][j] + p2 * dp[i][j+1] + p3 * dp[i+1][j] + 2*(p2+p3)

移項（p1 ≠ 1 保證）：

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

逆序計算：i=n..1, j=m..1。

參考代碼 (C++)

#include 
using namespace std;
double p1[1005][1005], p2[1005][1005], p3[1005][1005], dp[1005][1005];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                cin >> p1[i][j] >> p2[i][j] >> p3[i][j];
        for (int i = n-1; i >= 0; --i)
            for (int j = m-1; j >= 0; --j) {
                if (i == n-1 && j == m-1) continue;
                if (fabs(p1[i][j] - 1.0) < 1e-9) continue; // 不動概率1，無法到達
                dp[i][j] = (p2[i][j] * dp[i][j+1] + p3[i][j] * dp[i+1][j] + 2.0) / (1.0 - p1[i][j]);
            }
        cout << fixed << setprecision(3) << dp[0][0] << '\n';
    }
    return 0;
}

關鍵點

• 期望 DP 核心：E = Σ p_i * (cost_i + E_next)，解線性方程。
• 「不動」產生自迴路，移項消去 dp[i][j] 系數。
• 每步消耗 2，故常數項為 2*(p2+p3) = 2*(1-p1)，化簡後分子為 2。
• 邊界：p1=1 表示死循環，題目保證有解或需輸出特殊值（代碼中跳過）。

複雜度

O(n*m) 狀態，每狀態 O(1) 轉移。n,m ≤ 1000 共 10⁶ 狀態，極快。

總結

• 帶自迴路的期望 DP 標準套路：E = (Σ p_i E_i + cost) / (1 - p_self)。
• 逆拓撲序計算（從終點反推）。
• 雙精度足夠，輸出保留 3 位小數。