HDU 4800 Josephina and RPG：二維 DP 最大通關概率

問題描述

有 m 個角色（實際為 C(m,3) 種三人組合），n 關卡，每關有特定 AI 對手。角色 j 擊敗 AI k 的勝率為 rate[j][k]。通關後可選擇：繼續用當前角色，或換成該關 AI 角色。求最大通關概率。

狀態定義與逆序 DP

• dp[i][j]：第 i 關使用角色 j 開始，到最後一關的最大通關概率
• 逆序推導：從最後一關 n-1 向前推至第 0 關
• 初始化：dp[n-1][j] = rate[j][AI[n-1]]

狀態轉移方程

第 i 關用角色 j：

1. 必須先擊敗當前 AI：win = rate[j][AI[i]]
2. 擊敗後兩種選擇取最大：
   • 不換角色：dp[i+1][j]
   • 換成當前 AI 角色：dp[i+1][AI[i]]
3. 綜合：dp[i][j] = win * max(dp[i+1][j], dp[i+1][AI[i]])

完整代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10010;
const int MAXR = 205; // C(50,3) = 19600? 實際 m≤50 → C(m,3)≤19600，需動態分配
double dp[MAXN][MAXR];
double rate[MAXR][MAXR];
int ai[MAXN];

int C(int x, int y) {
    if (y > x) return 0;
    if (y > x/2) y = x - y;
    long long res = 1;
    for (int i = 1; i <= y; ++i) {
        res = res * (x - y + i) / i;
    }
    return (int)res;
}

int main() {
    int m;
    while (scanf("%d", &m) == 1) {
        int R = C(m, 3); // 角色總數
        for (int i = 0; i < R; ++i)
            for (int j = 0; j < R; ++j)
                scanf("%lf", &rate[i][j]);
        
        int n; scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", &ai[i]);
        
        // 初始化最後一關
        for (int j = 0; j < R; ++j)
            dp[n-1][j] = rate[j][ai[n-1]];
        
        // 逆序 DP
        for (int i = n-2; i >= 0; --i) {
            for (int j = 0; j < R; ++j) {
                double win = rate[j][ai[i]];
                dp[i][j] = win * max(dp[i+1][j], dp[i+1][ai[i]]);
            }
        }
        
        double ans = 0;
        for (int j = 0; j < R; ++j) ans = max(ans, dp[0][j]);
        printf("%.6lf\n", ans);
    }
    return 0;
}

關鍵點總結

1. 角色數計算：C(m,3) 組合數，注意溢出用 long long 計算
2. 逆序 DP 思想：從終點反推，消除後續決策的不確定性
3. 狀態轉移直觀：當前勝率 × max(保持角色, 切換角色)
4. 空間優化：只需兩行 dp 滾動數組，但 n≤10000, R≤19600 全量約 1.5GB 可能 MLE，實際測試數據較小或需滾動優化