codeforces 148D Bag of mice(概率dp)

题意:给你w个白色小鼠和b个黑色小鼠,把他们放到袋子里,princess先取,dragon后取,princess取的时候从剩下的当当中任意取一个,dragon取得时候也是从剩下的时候任取一个,但是取完之后会随机跳出来一个。取到每个小鼠的概率是一样的,跳出的也是一样的。先取到白色的小鼠赢,问最后princess能赢的概率。

思路:概率dp,如果把princess能赢的分成两种情况,那么这个题就是递推了,我是用记忆化搜索写的。首先,用dp[i][j]表示袋子当中还有i个白色的,j个黑色的princess能取赢的概率。那么有两种情况:

1.这一步能取赢,那么就是直接取到白色的,概率为i/(i+j);

2.这一步取不赢,那么当前一定是取到黑色的,因为最后要让princess赢,所以,接着dragon也取不赢,现在还有一个问题是,跳出的小鼠的颜色,那么又分为两种情况:

  1). 跳出的为白色的。概率就是j/(i+j)*(j-1)/(i+j-1)*(i)/(i+j-2)*dp[i-1][j-2]

  2). 跳出的位黑色的。概率就是j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3]

推到这里基本上就出来了,剩下的边界条件了。如果i==0,那么概率一定是0,   如果i>0&&j==0那么概率一定为1.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = ;
double dp[maxn][maxn];
double dfs(int i, int j)
{
if (i <= || j < ) return ;
if (i > && j == ) return dp[i][] = ;
if (dp[i][j] != -) return dp[i][j];
double t1 = (double)i / (i + j);
double t2 = (double)j / (i + j);
dp[i][j] = t1;
if (i + j > )
{
double t3 = dfs(i, j - ) * (j - ) / (i + j - ) * (j - ) / (i + j - );
double t4 = dfs(i - , j - ) * (j - ) / (i + j - ) * (i) / (i + j - );
t2 *= (t3 + t4);
dp[i][j] = t1 + t2;
}
return dp[i][j];
}
int main()
{
int w, b;
scanf("%d%d", &w, &b);
//memset(dp, -1, sizeof(dp));
for (int i = ; i <= w; i++)
for (int j = ; j <= b; j++)
dp[i][j] = -;
printf("%.9f\n", dfs(w, b)); return ;
}
上一篇:【题解】 Codeforces 662A Gambling Nim (线性基)


下一篇:TCPCopy 使用方法