Codeforces 148D Bag of mice：概率 DP 計算公主勝率

題目大意

袋中 w 白鼠、b 黑鼠。公主、龍輪流摸鼠，公主先摸。摸到白鼠者勝。龍摸完後會隨機跑掉一隻鼠 (不算摸中)。求公主勝率。w,b ≤ 1000。

DP 狀態定義

• `win[w][b]`：w 白、b 黑時，輪到**公主**摸的勝率。
• `lose[w][b]`：w 白、b 黑時，輪到**龍**摸時，公主最終勝率 (即龍輸的概率)。

轉移方程推導

**公主回合 (win)：**

• 摸白：概率 `w/(w+b)`，直接勝。
• 摸黑：概率 `b/(w+b)`，轉入龍回合 `lose[w][b-1]`。
• `win[w][b] = w/(w+b) + b/(w+b) * lose[w][b-1]`

**龍回合 (lose)：**

• 龍摸白：概率 `w/(w+b)`，公主輸 → 貢獻 0。
• 龍摸黑：概率 `b/(w+b)`，剩 (w, b-1)，隨機跑掉一隻：
  • 跑白：概率 `w/(w+b-1)`，狀態變 `(w-1, b-1)`，公主勝率 `win[w-1][b-1]`。
  • 跑黑：概率 `(b-1)/(w+b-1)`，狀態變 `(w, b-2)`，公主勝率 `win[w][b-2]`。
• `lose[w][b] = b/(w+b) * [ w/(w+b-1)*win[w-1][b-1] + (b-1)/(w+b-1)*win[w][b-2] ]`

邊界條件

• `win[w][0] = 1` (全白必勝)
• `win[0][b] = 0` (無白必輸)
• `lose[w][0] = 0` (龍摸必中白)
• `lose[0][b] = 0` (無白公主必輸)
• 數組下標檢查防止越界 (b-1, b-2 < 0 時項為 0)。

代碼實現 (C++)

#include 
#include 
using namespace std;

double win[1005][1005], lose[1005][1005];

int main() {
    int w, b;
    while (~scanf("%d%d", &w, &b)) {
        for (int i = 0; i <= w; i++) {
            for (int j = 0; j <= b; j++) {
                win[i][j] = lose[i][j] = 0;
            }
        }
        for (int i = 1; i <= w; i++) win[i][0] = 1.0;
        
        for (int i = 1; i <= w; i++) {
            for (int j = 1; j <= b; j++) {
                double total = i + j;
                // 公主回合
                win[i][j] = i / total; // 摸白
                win[i][j] += (j / total) * lose[i][j-1]; // 摸黑
                
                // 龍回合
                if (j >= 1) {
                    double pDragonBlack = j / total;
                    double remTotal = total - 1;
                    if (remTotal > 0) {
                        // 跑白
                        if (i >= 1) lose[i][j] += pDragonBlack * (i / remTotal) * win[i-1][j-1];
                        // 跑黑
                        if (j >= 2) lose[i][j] += pDragonBlack * ((j-1) / remTotal) * win[i][j-2];
                    }
                }
            }
        }
        printf("%.9f\n", win[w][b]);
    }
    return 0;
}

關鍵點

• 雙 DP 表互相引用，按 `w` 從小到大、`b` 從小到大填表 (拓撲序)。
• 概率計算用 `double`，輸出 `%.9f` 滿足 1e-9 精度。
• 邊界 `j=1` 時 `win[i][j-2]` 不存在，代碼中 `if (j>=2)` 守護。