Codeforces 148D Bag of Mice

链接

传送门

题意

有$w$只白老鼠和$b$只黑老鼠,龙和公主轮流取,取到每只老鼠的概率相同,公主先取,龙取完之后会有一只老鼠跑掉。先取到白老鼠的胜利,如果没有人取到白老鼠,龙胜利。输出公主胜利的概率。

思路

定义状态$d[i][j]$为剩余$i$只白老鼠,$j$只黑老鼠是公主胜利的概率。只剩白老鼠时,概率为1;只剩黑老鼠时,概率为0。当公主和龙都取到黑老鼠时,可以根据跑掉的老鼠的颜色进行转移。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int maxn = 1010;
double dp[maxn][maxn];
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;
}
for (int i = 1; i <= w; ++i) {
for (int j = 1; j <= b; ++j) {
dp[i][j] = double(i) / (i + j);
if (j >= 3) {
dp[i][j] += double(j) / (i + j) * double(j - 1) / (i + j - 1) * double(j - 2) / (i + j - 2) * dp[i][j - 3];
}
if (j >= 2) {
dp[i][j] += double(j) / (i + j) * double(j - 1) / (i + j - 1) * double(i) / (i + j - 2) * dp[i - 1][j - 2];
}
}
}
printf("%.10f\n", dp[w][b]); return 0; }

支付宝扫码领红包