【DP】【概率】红蓝球

概率】红蓝球"/>

【DP】【概率】红蓝球

有 n 个红球和 m 个蓝球，A，B，C 三个人，轮流取球。若 A 取到红球则 A 胜利，若 B 取到红球则 B 胜利，C只负责取球捣乱，不参与胜负。若最后全部球取完后 A 没有拿到红球，则 B 胜利，求 A 胜利的概率。
输入：m, n
输出：A 胜利的概率，保留 5 位小数（补零）

样例输入: 3 4 （3 个红球，4 个蓝球）
样例输出 0.62857

  就是 A、B谁拿了红的就赢，结束，最后没人拿到红，算 B 赢，问 A 赢的概率。牛客网上看，BFS 结果好像对，但是超内存了，就想到应该 bottom-up 不应该 top-down 的。（printf 自动四舍五入）。

#include <iostream>
#include <vector>
using namespace std;double process(int n, int m) {vector<vector<double>> dp(n + 1, vector<double>(m + 1));for (int i = 1; i <= n; ++i) dp[i][0] = 1;for (int i = 0; i <= m; ++i) dp[0][i] = 0;dp[1][1] = 0.5;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {const double di = i, dj = j, dij = di + dj;if (i + j < 3 || j <= 1)dp[di][dj] = di / dij;else if (j < 3)dp[i][j] = di / dij + dj / dij * (dj - 1) / (dij - 1) * di / (dij - 2) * dp[i - 1][j - 2];elsedp[i][j] = di / dij +dj / dij * (dj - 1) / (dij - 1) * (dj - 2) / (dij - 2) * dp[i][j - 3] +dj / dij * (dj - 1) / (dij - 1) * di / (dij - 2) * dp[i - 1][j - 2];}}return dp[n][m];
}int main() {int n, m;cin >> n >> m;printf("%.5lf\n", process(n, m));
}

  dp[i][j] 表示 i 个红球，j 个蓝球的情况下 A 获胜的概率。显然 j == 0 时，A必赢；i == 0时，A必输；一个红球，一个蓝球，A 获胜概率 50%。
  上边的第一种情况（i + j < 3 || j <= 1），也就是最多三个人各摸一个球肯定就结束了，这时dp[i][j] 就是 A 上来就摸到红球的概率： i i + j \frac{i}{ i + j} i+ji​
  上边的第二种情况（j < 3），dp[i][j] 有两个组成部分：

1、 i i + j \frac{i}{ i + j} i+ji​：A直接摸到红球的概率

2、 j i + j ⋅ j − 1 i + j − 1 ⋅ i i + j − 2 ⋅ d p [ i − 1 ] [ j − 2 ] \frac{j}{i+j} \cdot \frac{j - 1}{i+j-1} \cdot \frac{i}{i+j-2} \cdot dp[i - 1][j - 2] i+jj​⋅i+j−1j−1​⋅i+j−2i​⋅dp[i−1][j−2]：A蓝、B蓝、C红，之后 A红 的概率

  上边的第三种情况，也就是最通用的情况下，dp[i][j] 有三个组成部分：

1、 i i + j \frac{i}{ i + j} i+ji​：A直接摸到红球的概率

2、 j i + j ⋅ j − 1 i + j − 1 ⋅ j − 2 i + j − 2 ⋅ d p [ i ] [ j − 3 ] \frac{j}{ i + j} \cdot \frac{j - 1}{i+j-1} \cdot \frac{j - 2}{i+j-2} \cdot dp[i][j - 3] i+jj​⋅i+j−1j−1​⋅i+j−2j−2​⋅dp[i][j−3]：A蓝、B蓝、C蓝，之后 A红 的概率

3、 j i + j ⋅ j − 1 i + j − 1 ⋅ i i + j − 2 ⋅ d p [ i − 1 ] [ j − 2 ] \frac{j}{i+j} \cdot \frac{j - 1}{i+j-1} \cdot \frac{i}{i+j-2} \cdot dp[i - 1][j - 2] i+jj​⋅i+j−1j−1​⋅i+j−2i​⋅dp[i−1][j−2]：A蓝、B蓝、C红，之后 A红 的概率