题目链接: https://vjudge.net/contest/537778#problem/H
题意
有一袋老鼠，里面有 w 只白鼠， b 只黑鼠。现在公主和龙轮流从里面拿出一只老鼠。
当龙拿完老鼠后，会有另外一只老鼠受惊从袋子里跑出来。
公主先手，问拿到白鼠的第一个人是公主的概率是多少。
(0 ≤ w, b ≤ 1000)
思路
先分类讨论下公主取胜的概率。
- 公主拿到一只白鼠，概率为
w/(w+b) - 公主拿到一只黑鼠，概率为
b/(w+b)，接下来要取胜就得期望龙拿不到白鼠了 - 龙拿到一只黑鼠，然后跑掉一只白鼠，概率为
(b-1)/(w+b-1) * (w)/(w+b-2) - 然后公主拿到一只白鼠，概率为
(w-1)/(w+b-3) - 龙拿到一只黑鼠，然后跑掉一只黑鼠，概率为
(b-1)/(w+b-1) * (b-2)/(w+b-2) - 然后公主拿到一只白鼠，概率为
(w)/(w+b-3)
然后写下状态转移方程即可。
设有w白鼠和b黑鼠时公主拿到第一只白鼠的概率为 dp[w][b]。
考虑无后效性更新状态，每一次状态都从更多的老鼠转移到更少的老鼠。所以我们要从小往大更新。
复杂度: O(w·b)
代码
代码实现
#include <iostream>
#include <iomanip>
#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL std::cout << '\n';
const int maxN = 1e3+5;
double dp[maxN][maxN];
int main() {
std::ios::sync_with_stdio(0); std::cin.tie(0);
int w, b;
std::cout << std::setprecision(15);
std::cin >> w >> b;
orep(i, 1, w+1) { dp[i][0] = 1; }
orep(i, 1, b+1) { dp[0][i] = 0; }
orep(i, 1, w+1) {
orep(j, 1, b+1) {
dp[i][j] = 1.0*i/(i+j);
dp[i][j] += j<3
? 0
: 1.0*j/(i+j) * 1.0*(j-1)/(i+j-1) * 1.0*(j-2)/(i+j-2) * dp[i][j-3];
dp[i][j] += i<1||j<2
? 0
: 1.0*j/(i+j) * 1.0*(j-1)/(i+j-1) * 1.0*i/(i+j-2) * dp[i-1][j-2];
}
}
std::cout << dp[w][b];
return 0;
}