Codeforces 540D(概率DP)

发表于 | 分类于 | | + s

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

#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;
}
------ 本文结束 ------