Codeforces 540D(概率DP)

Codeforces 540D
设$dp(i,j,k)$为石头有$i$人,剪刀有$j$人,纸有$k$人的状态存在的概率。
则转移方程为
$$dp(i,j,k)= dp(i+1,j,k) \times P_1 + dp(i,j+1,k) \times P_2 + dp(i,j,k+1) \times P_3$$
$dp(r, s, p) = 1.0$
但是这样不好转移,因为概率是很难算的,那我们改一下原方程:
设$sum=ij+ik+jk$
$dp(i-1, j, k)=dp(i, j, k) \times \frac{ik}{sum}​$
$dp(i, j-1, k)=dp(i, j, k) \times \frac{ij}{sum}​$
$dp(i, j, k-1)=dp(i, j, k) \times \frac{jk}{sum}​$
这样就方便转移了,最后的答案累加一下必胜的状态的存在概率即可。

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5;
int r, s, p;
db dp[MAXN][MAXN][MAXN];
void clean() {
ms(dp, 0);
}
void solve() {
clean();
dp[r][s][p] = 1.0;
for (int i=r;i>=1;i--) {
for (int j=s;j>=1;j--) {
for (int k=p;k>=1;k--) {
db sum = (db)(i * j) + (db)(i * k) + (db)(j * k);
dp[i-1][j][k] += dp[i][j][k] * ((db)(i * k) / sum);
dp[i][j-1][k] += dp[i][j][k] * ((db)(i * j) / sum);
dp[i][j][k-1] += dp[i][j][k] * ((db)(j * k) / sum);
}
}
}
db ans1 = 0.0, ans2 = 0.0, ans3 = 0.0;
for (int i=1;i<=100;i++) {
for (int j=0;j<=100;j++) {
ans1 += dp[i][j][0];
ans2 += dp[0][i][j];
ans3 += dp[j][0][i];
}
}
printf("%.12f %.12f %.12f\n", ans1, ans2, ans3);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin); freopen("1.out", "w", stdout);
#endif
scanf("%d%d%d", &r, &s, &p), solve();
fclose(stdin); fclose(stdout);
return 0;
}

------ 本文结束 ------