HDU 3853 LOOPS：期望 DP 逆向推導計算最小功耗

問題描述

網格 r × c，從 (1,1) 走到 (r,c)。每步消耗 2 功率。從 (i,j) 有三種移動概率：留原地 p0、右 p1、下 p2（p0+p1+p2=1）。求到達終點期望功耗。若 p0=1 導致無法到達，輸出對應處理（題目保證有解或特殊判斷）。

DP 定義與逆向轉移

設 dp[i][j] 為從 (i,j) 到 (r,c) 的期望功耗。終態 dp[r][c] = 0。對於 (i,j) ≠ (r,c)：

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)

關鍵：若 1 - p0 ≈ 0（即 p0 ≈ 1），分母極小，期望趨向無限大（無法到達）。代碼中用 eps 判斷並跳過更新（保持初值 0），最終輸出 dp[1][1]。

計算順序

逆序填表：i = r..1, j = c..1，保證右/下狀態已計算。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const double EPS = 1e-9;
double dp[MAXN][MAXN];
double p[MAXN][MAXN][3]; // 0:stay, 1:right, 2:down

int main() {
    int r, c;
    while (cin >> r >> c) {
        for (int i=1;i<=r;++i)
            for (int j=1;j<=c;++j)
                for (int k=0;k<3;++k)
                    cin >> p[i][j][k];
        memset(dp, 0, sizeof dp);
        dp[r][c] = 0;
        for (int i=r;i>=1;--i) {
            for (int j=c;j>=1;--j) {
                if (i==r && j==c) continue;
                double stay = p[i][j][0];
                if (fabs(1.0 - stay) < EPS) continue; // p0=1, 無法前進
                dp[i][j] = (p[i][j][1] * dp[i][j+1] + p[i][j][2] * dp[i+1][j] + 2) / (1.0 - stay);
            }
        }
        cout << fixed << setprecision(3) << dp[1][1] << "\n";
    }
    return 0;
}

複雜度

• 時間 O(r·c)，空間 O(r·c)。
• r,c ≤ 1000 時約 1e6 狀態，極快。

關鍵點總結

1. 期望 DP 逆向思維：從終點反推起點，利用線性期望公式解方程。
2. 自環處理：p0 * dp[i][j] 移至左邊，分母 1-p0 為實際前進概率。
3. 數值穩定：EPS 判斷 p0=1 避免除零；若題目保證可達則無需特判。
4. 邊界：dp[r][c+1], dp[r+1][c] 初始為 0，不影響計算（對應邊界無法右/下移）。

本題是期望 DP 中「含自環轉移」的標準範例，展示了如何通過代數變換消除自環項，逆向填表求解。