CodeForces 540D (Bad Luck Island)[概率DP]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/540/D

概率DP，dp[i][j][k]表示还剩i个石头，j个剪刀，k个布的概率。

以石头减少为例，dp[i][j][k]转移到dp[i-1][j][k]的概率为i*k/(i*j+j*k+i*k)
这样就有dp[i-1][j][k]+=dp[i][j][k]*(1.0*i*k)/(i*j+j*k+i*k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
using namespace std;
const int maxn=109;
double dp[maxn][maxn][maxn];
int main() {
    int r,s,p;
    scanf("%d%d%d",&r,&s,&p);
    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--) {
        dp[i-1][j][k]+=dp[i][j][k]*(1.0*i*k)/(i*j+j*k+i*k);
        dp[i][j-1][k]+=dp[i][j][k]*(1.0*i*j)/(i*j+j*k+i*k);
        dp[i][j][k-1]+=dp[i][j][k]*(1.0*j*k)/(i*j+j*k+i*k);
    }
    double ans1=0.0,ans2=0.0,ans3=0.0;
    for (int i=1;i<maxn;i++)
        for (int j=0;j<maxn;j++) {
            ans1 += dp[i][j][0];
            ans2 += dp[0][i][j];
            ans3 += dp[j][0][i];
        }
    printf("%.10f %.10f %.10f",ans1,ans2,ans3);
}