题意:给你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 ;
}