链接
传送门
题意
有\(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;
}
|