期望/概率DP - mengh04の小窝

封面来源
MISSILE228-大雨の中で泣くとよい

例题1-Bag of mice#

题目来源

题目大意#

目标：计算公主获胜的概率。

游戏规则：

开局: 袋子里有 w 只白鼠， b 只黑鼠。
胜利: 谁第一个摸到白鼠，谁就赢。
顺序: 公主先手，然后是龙，轮流进行。
公主的回合: 从袋子里摸 1 只鼠。
龙的回合: 龙摸 1 只鼠，然后袋子里剩下的鼠会再随机跳出 1 只。
平局: 如果鼠鼠都摸完了/跳完了还没人摸到白鼠，算龙赢。

定义 DP 状态#

在动态规划（DP）中，我们需要一个“状态”来唯一描述当前的局面。思考一下，在这个游戏中，决定未来的关键信息是什么？

很简单，就是：

袋子里还剩几只白鼠？
袋子里还剩几只黑鼠？
现在轮到谁操作？（因为公主和龙的操作不同）

因此，我们可以定义一个三维的状态 dp[i][j][k]：

i: 代表袋子里还剩 i 只白鼠。
j: 代表袋子里还剩 j 只黑鼠。
k: 代表当前回合的玩家。我们可以约定 k = 0 代表公主，k = 1 代表龙。

那么 dp[i][j][k] 的值代表什么呢？它就代表：在当前状态下，公主最终获胜的总概率。

我们最初的局面是 $w$ 只白鼠， $b$ 只黑鼠，轮到公主。所以，我们的最终目标就是求出 dp[w][b][0] 的值。

公主回合的状态转移方程#

当前状态是 dp[w][b][0]，表示有 $w$ 只白鼠， $b$ 只黑鼠，轮到公主。袋子里总共有 $w+b$ 只鼠鼠。

公主伸手一摸，只有两种可能的结果：

摸到了白鼠
- 概率: 袋子里有 $w$ 只白鼠，所以摸到的概率是 $\frac{w}{w+b}$ 。
- 结果: 公主直接获胜！她获胜的概率是 1。
- 对总概率的贡献: $\frac{w}{w+b}\times 1$ 。
摸到了黑鼠
- 概率: 袋子里有 $b$ 只黑鼠，所以摸到的概率是 $\frac{b}{w+b}$ 。
- 结果: 游戏继续。现在袋子里剩下 $w$ 只白鼠和 $b - 1$ 只黑鼠，并且轮到龙了。
- 对总概率的贡献: 在这个分支下，公主获胜的概率，根据我们之前的定义，就是 dp[w][b - 1][1]。所以这部分的贡献就是 $\frac{b}{w+b}\times dp[w][b - 1][1]$ 。

把这两种可能加起来，我们就得到了公主回合的状态转移方程：

dp[w][b][0] = \frac{w}{w+b}\times 1 + \frac{b}{w+b}\times dp[w][b - 1][1]

龙回合的状态转移方程#

当前状态是 dp[w][b][1]，表示有 $w$ 只白鼠， $b$ 只黑鼠，轮到龙了。龙的操作分两步：1. 龙摸一只 -> 2. 鼠鼠自己跳一只。

我们来分解一下：

第一步：龙先摸#

龙从 $w+b$ 只鼠鼠里摸一只。

龙摸到了白鼠
- 概率: $\frac{w}{w+b}$ 。
- 结果: 龙赢了，游戏结束！公主就输了，所以公主获胜的概率是0。
龙摸到了黑鼠
- 概率: $\frac{b}{w+b}$
- 结果: 游戏继续！现在进入第二步：鼠鼠要自己跳出来了。此时袋子里还剩 $w$ 只白鼠和 $b - 1$ 只黑鼠。

重点：只有在龙摸到黑鼠的情况下，公主才有可能赢。所以我们只需要关注这条路线。

第二步：鼠鼠自己跳#

在龙摸了一只黑鼠之后，袋子里还剩 $w+(b−1)$ 只鼠鼠。现在，其中一只会自己跳出来。

跳出来的是白鼠：
- 概率: 此时白鼠有 $w$ 只，所以概率是 $\frac{w}{w+(b−1)}$ 。
- 结果: 袋子状态变为 $w−1$ 只白鼠， $b−1$ 只黑鼠，并且轮到公主了。接下来公主获胜的概率就是 dp[w-1][b-1][0]。
跳出来的是黑鼠：
- 概率: 此时黑鼠有 $b - 1$ 只，所以概率是 $\frac{b - 1}{w + (b - 1)}$ 。
- 结果: 袋子状态变为 $w$ 只白鼠， $b - 2$ 只黑鼠，并且轮到公主了。接下来公主获胜的概率就是 dp[w][b - 2][0]。

整合龙的回合现在我们把龙的回合所有可能性整合起来。dp[w][b][1] 的值，就是 (龙摸到黑鼠的概率) x (后续情况下公主获胜的概率)。

后续情况就是上面“鼠鼠自己跳”的两种可能，所以我们要把它们加起来：

dp[w][b][1]= \frac{b}{w+b} \times \left( \frac{w}{w+b-1} \times dp[w-1][b-1][0]+ \frac{b-1}{w+b-1} \times dp[w][b-2][0] \right)

这个就是龙回合的完整状态转移方程啦！

边界条件#

边界条件是递归的终点，也就是我们能直接确定答案的简单情况。

没有白鼠了 (w = 0): 公主不可能赢。所以 dp[0][j][k] = 0。

没有黑鼠了 (b = 0):

如果轮到公主 (k = 0)，她面前全是白鼠，必胜！所以 dp[w][0][0] = 1。

如果轮到龙 (k = 1)，他面前全是白鼠，他必胜，公主就输了。所以 dp[w][0][1] = 0。

鼠鼠不够了: 在龙的回合，我们计算时会遇到 b - 1 或 b - 2 这样的情况。如果 b 本身就很小，可能导致鼠鼠数量变为负数。这些都是不可能发生的非法状态，它们的概率贡献应该是 0。

代码实现#

1
// 引入万能头文件，包含了算法竞赛中常用的大部分库
2
#include <bits/stdc++.h>
3
// 使用标准命名空间
4
using namespace std;
5
// 定义一个i64类型别名，代表long long，让代码更简洁
6
using i64 = long long;
7

8
int main() {
9
    // 关闭C++标准流与C标准流的同步，加速cin和cout
10
    ios::sync_with_stdio(false);
11
    // 解除cin和cout的绑定，进一步加速输入输出
12
    cin.tie(nullptr);
13

14
    // w: 白鼠鼠的数量, b: 黑鼠鼠的数量
15
    int w, b;
16
    cin >> w >> b;
17

18
    // 创建一个三维的dp表用于记忆化搜索
19
    // vector的现代C++构造方式，非常优雅~
20
    // dp[i][j][k] 表示剩下 i 只白鼠, j 只黑鼠, 轮到 k (0:公主, 1:龙) 时公主的胜率
21
    // 使用 long double 来保证精度，-1.0L 作为未计算的标记
22
    vector dp(w + 1, vector(b + 1, array<long double, 2>({-1.0L, -1.0L})));
23

24
    // --- 预处理一些边界条件 ---
25
    // 虽然递归函数里也有边界判断，但预先设置可以减少一些递归深度
26

27
    // 当没有白鼠(w=0)时，公主不可能赢，胜率为0
28
    for (int i = 1; i <= b; i++) {
29
        dp[0][i][0] = 0; // 轮到公主，没白的，输
30
        dp[0][i][1] = 0; // 轮到龙，没白的，输 (这里主人代码只写了[0][1][1]，猫娘帮你补全啦)
31
    }
32

33
    // 当没有黑鼠(b=0)时
34
    for (int i = 1; i <= w; i++) {
35
        dp[i][0][0] = 1; // 轮到公主，全是白的，必胜
36
        dp[i][0][1] = 0; // 轮到龙，全是白的，龙必胜，公主输
37
    }
38

39
    // w=0, b=0 的特殊情况
40
    dp[0][0][0] = 0; // 没鼠鼠了，公主输
41
    dp[0][0][1] = 0; // 没鼠鼠了，龙赢
42

43
    // 定义一个递归lambda函数 `dfs` 来进行计算
44
    // auto&& self 的语法是C++17开始支持的，用于方便地在lambda内部递归调用自身
45
    // op -> operation, 0 代表公主的回合, 1 代表龙的回合
46
    auto dfs = [&](auto &&self, int w, int b, int op) -> long double {
47
        // --- 递归的边界/基本情况 ---
48

49
        // 如果w或b已经在dp表范围外，说明是预处理过的边界，直接返回dp表的值
50
        // （这里主人的代码是直接判断w==0和b==0，猫娘稍微调整下注释逻辑让它更清晰）
51
        if (w == 0) {
52
            return 0.0L; // 没有白鼠了，公主必输
53
        }
54
        if (b == 0) {
55
            return op == 0 ? 1.0L : 0.0L; // 没有黑鼠了，看轮到谁
56
        }
57
        // 当龙的回合 b=1 时，会递归到 b-2=-1，这是非法状态，公主胜率为0
58
        if (b < 0) {
59
            return 0.0L;
60
        }
61

62
        // --- 记忆化检查 ---
63
        // 如果当前状态已经计算过，直接返回存储的结果，避免重复计算
64
        if (dp[w][b][op] > -0.5L) { // 用 > -0.5L 判断浮点数是否等于-1.0L更稳健
65
            return dp[w][b][op];
66
        }
67

68
        long double res = 0; // 用来存储当前状态的结果
69

70
        // --- 状态转移 ---
71

72
        if (!op) { // op == 0, 公主的回合
73
            // 公主的胜率 = (摸到白的概率 * 1) + (摸到黑的概率 * 接下来轮到龙时公主的胜率)
74
            res = 1.0L * w / (w + b) + 1.0L * b / (w + b) * self(self, w, b - 1, 1);
75
        } else { // op == 1, 龙的回合
76
            // 公主的胜率只在龙摸到黑鼠时才不为0
77
            // 龙摸到白鼠的概率是 w/(w+b)，那种情况公主胜率为0，所以不用加
78
            if (w + b - 1 > 0) { // 防止龙摸完黑鼠后分母为0 (即w=0, b=1的情况)
79
                 res = 1.0L * b / (w + b) * ( // 龙摸到黑鼠的概率
80
                    1.0L * w / (w + b - 1) * self(self, w - 1, b - 1, 0) +     // 之后跳出来的是白鼠
81
                    1.0L * (b - 1) / (w + b - 1) * self(self, w , b - 2, 0) // 之后跳出来的是黑鼠
82
                );
83
            }
84
            // 如果 w + b - 1 <= 0, 说明龙摸完就没了，龙赢，公主胜率为0，res初始值0就是正确答案
85
        }
86

87
        // 将计算结果存入dp表并返回
88
        return dp[w][b][op] = res;
89
    };
90

91
    // 从初始状态 (w, b, 0) 开始递归计算
92
    // 结果会存储在 dp[w][b][0] 中
93
    dfs(dfs, w, b, 0);
94

95
    // 以固定格式输出小数点后20位，保证精度
96
    cout << fixed << setprecision(20) << dp[w][b][0] << "\n";
97

98
    return 0;
99
}