抓老鼠 codeForce 148D - Bag of mice 概率DP

设dp[i][j]为有白老鼠i只，黑老鼠j只时轮到公主取时，公主赢的概率。

那么当i = 0 时，为0

当j = 0时，为1

公主可直接取出白老鼠一只赢的概率为i/(i+j)

公主取出了黑老鼠，龙必然也要取出黑老鼠公主才能赢，跑出来的老鼠有两种可能

跑出来的是黑老鼠，公主赢的概率为dp[i][j] += j/（i+j）*（j-1）/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3].（j>=3）

跑出来的是白老鼠，公主赢的概率为dp[i][j] += j/（i+j）*（j-1）/(i+j-1)*i/(i+j-2)*dp[i-1][j-2].（j>=2）

贴代码：

 #include <cstdio>

 #define N 1005

 double dp[N][N];

 int main()

 {

 //    freopen("in.c","r",stdin);

     int w,b;

     scanf("%d%d",&w,&b);

     for(int i=; i<=w; ++i) dp[i][] =;

     for(int i=; i<=b; ++i) dp[][i] =;

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

     {

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

         {

             dp[i][j] = (double)i/(i+j);

             if(j >= ) dp[i][j] += (double)j/(i+j)*(double)(j-)/(i+j-)*(double)(j-)/(i+j-)*dp[i][j-];

             if(j >= ) dp[i][j] += (double)j/(i+j)*(double)(j-)/(i+j-)*(double)i/(i+j-)*dp[i-][j-];

         }

     }

     printf("%.9lf\n",dp[w][b]);

     return ;

 }

巴特西

抓老鼠 codeForce 148D - Bag of mice 概率DP

最新文章

热门文章