CodeForces 540D--Bad Luck Island（概率DP）

貌似竟然是我的第一道概率DP。。

手机码代码真不舒服。。。。

/************************************************

Memory: 67248 KB		Time: 31 MS

Language: GNU G++ 4.9.2		Result: Accepted

************************************************/

/**

一个岛上住着一些石头,剪刀,布，他们互相之间两两随机碰面，如果不是一个种族，一个会杀死另一个

最后只会活下一个种族，求最后活下来的是各个种族的概率

这tm原来是一道概率dp，那我也不会啊 =。=

想一想。。。dp[i][j][k] 表示三个种族分别剩下i,j,k的概率

那么初始dp[a][b][c] = 1;

a和b碰面的概率是i*j/i*j+j*k+k*i,所以死一只b的概率是i*j/i*j+j*k+k*i(如果不是看别人题解，我绝对想不到啊啊，概率渣)

那么由dp[i][j][k]到dp[i][j-1][k]的概率是i*j/i*j+j*k+k*i

对于dp[i][j][k]来说，有三种情况可以到达它，dp[i+1][j][k],dp[i][j+1][k],dp[i][j][k+1]

所以dp[i][j][k]=dp[i+1][j][k] * k*(i+1) / ((i+1)*j + j*k + k*(i+1)) +

                dp[i][j+1][k] * i*(j+1) / (i*(j+1) + k*i + (j+1)*k) +

                dp[i][j][k+1] * j*(k+1) / (j*(k+1) + j*i + (k+1)*i)

还有一点问题就是。。当i,j,k中有两个为0的时候，表达式会出现分母为0的情况

考虑到其实dp[i][0][0]已经不能再转移了，所以判断一下

*/

#include<stdio.h>

double dp[205][205][205];

int main()

{

    int a, b, c;

    scanf("%d%d%d", &a, &b, &c);

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

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

    {

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

        {

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

            {

                if (i == a && j == b && k == c) continue;

                if (j || k)

                    dp[i][j][k] += dp[i + 1][j][k] * k * (i + 1) / (k * (i + 1) + j * k + (i + 1) * j);

                if (i || k)

                    dp[i][j][k] += dp[i][j + 1][k] * i * (j + 1) / (i * (j + 1) + (j + 1) * k + i * k);

                if (i || j)

                    dp[i][j][k] += dp[i][j][k + 1] * j * (k + 1) / (j * (k + 1) + j * i + (k + 1) * i);

                //printf("dp[%d][%d][%d]=%f\n", i, j, k, dp[i][j][k]);

            }

        }

    }

    double p1, p2, p3;

    p1 = p2 = p3 = 0;

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

        p1 += dp[i][0][0];

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

        p2 += dp[0][i][0];

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

        p3 += dp[0][0][i];

    printf("%.9f %.9f %.9f", p1, p2, p3);

    return 0;

}