Codeforces 148D Bag of Mice 概率DP遞推

問題描述

袋中有 w 白鼠、b 黑鼠。公主先抽，之後輪流。抽到白鼠者勝。龍每次抽完後（無論抽到何色），再隨機跳出一隻鼠。袋空無人抽到白鼠則龍勝。求公主獲勝概率。w,b ≤ 1000。

DP 狀態定義

dp[i][j] = 剩 i 白、j 黑時，公主獲勝概率。
初始：dp[0][j] = 0（無白鼠必敗），dp[i][0] = 1（無黑鼠必抽到白），dp[0][0] = 0。

轉移方程

公主回合：
- 抽白：i/(i+j) → 直接勝
- 抽黑：j/(i+j) → 進入龍回合，狀態 (i, j-1)

龍回合（條件：公主抽黑）：
- 龍抽白：i/(i+j-1) → 公主敗，貢獻 0
- 龍抽黑：(j-1)/(i+j-1) → 跳鼠階段，狀態 (i, j-2)

跳鼠階段（條件：雙方均抽黑）：
- 跳白：i/(i+j-2) → 轉移到 dp[i-1][j-2]
- 跳黑：(j-2)/(i+j-2) → 轉移到 dp[i][j-3]

完整遞推公式

dp[i][j] = i/(i+j)                                    // 公主直接抽白
         + j/(i+j) * (j-1)/(i+j-1) * [                // 公主黑、龍黑
             i/(i+j-2) * dp[i-1][j-2]                 // 跳白
           + (j-2)/(i+j-2) * dp[i][j-3]               // 跳黑
         ]
// 邊界：分母為0或參數<0時對應項為0

代碼實現

double dp[1005][1005];
int main() {
    int w, b; scanf("%d%d", &w, &b);
    for (int i = 0; i <= b; ++i) dp[0][i] = 0;
    for (int i = 1; i <= w; ++i) dp[i][0] = 1.0;
    
    for (int i = 1; i <= w; ++i) {
        for (int j = 1; j <= b; ++j) {
            dp[i][j] = (double)i / (i + j);
            if (j >= 2) {
                double p = (double)j / (i + j) * (j - 1) / (i + j - 1);
                if (j >= 3) dp[i][j] += p * (j - 2) / (i + j - 2) * dp[i][j - 3];
                dp[i][j] += p * i / (i + j - 2) * dp[i - 1][j - 2];
            }
        }
    }
    printf("%.9f\n", dp[w][b]);
}

複雜度

O(wb) = 10⁶ 狀態，每狀態 O(1) 轉移，總時間 ~ 10⁶，空間 8MB，完全可行。