codeforces 540D 概率dp

时间：2022-02-20 08:37:02

传送门

大概可以这样理解， 一开始有r个石头， p个布， s个剪刀， 每一天有其中的两个相遇， 如果两个是相同的种类， 什么都不会发生， 否则的话有一个会挂掉， 问最后每一种生存的概率。

dp[i][j][k]表示到达i个石头， j个布， s个剪刀的概率， 那么初始状态dp[r][p][s] = 1。 状态转移方程为dp[i-1][j][k] = i*k/tot*dp[i][j][k], tot是当前所有相遇的情况， tot = i*j+i*k+j*k。

最后求每一种的生存的概率， 如果是石头生存， 那么显然只要布为0， 石头的个数>0， 而剪刀的个数无论有多少个都可以。

 #include<bits/stdc++.h>

 using namespace std;

 #define pb(x) push_back(x)

 #define ll long long

 #define mk(x, y) make_pair(x, y)

 #define lson l, m, rt<<1

 #define mem(a) memset(a, 0, sizeof(a))

 #define rson m+1, r, rt<<1|1

 #define mem1(a) memset(a, -1, sizeof(a))

 #define mem2(a) memset(a, 0x3f, sizeof(a))

 #define rep(i, a, n) for(int i = a; i<n; i++)

 #define ull unsigned long long

 typedef pair<int, int> pll;

 const double PI = acos(-1.0);

 const double eps = 1e-;

 const int mod = 1e9+;

 const int inf = ;

 const int dir[][] = { {-, }, {, }, {, -}, {, } };

 double dp[][][];

 int main()

 {

     int a, b, c;

     cin>>a>>b>>c;

     mem(dp);

     dp[a][b][c] = 1.0;

     for(int i = a; i>=; i--) {

         for(int j = b; j>=; j--) {

             for(int k = c; k>=; k--) {

                 double tot = i*j+j*k+i*k;

                 dp[i-][j][k] += 1.0*(i*k)/tot*dp[i][j][k];

                 dp[i][j-][k] += 1.0*(j*i)/tot*dp[i][j][k];

                 dp[i][j][k-] += 1.0*(j*k)/tot*dp[i][j][k];

             }

         }

     }

     double ans1 = , ans2 = , ans3 = ;

     for(int i = ; i<=a; i++)

         for(int j = ; j<=b; j++)

             ans1 += dp[i][j][];

     for(int i = ; i<=b; i++)

         for(int j = ; j<=c; j++)

             ans2 += dp[][i][j];

     for(int i = ; i<=c; i++)

         for(int j = ; j<=a; j++)

             ans3 += dp[j][][i];

     printf("%.9f %.9f %.9f\n", ans1, ans2, ans3);

 }

相关文章