CodeForces - 148D Bag of mice——概率dp

CodeForces - 148D Bag of mice——概率dp

题意： 原来袋子里有w只白鼠和b只黑鼠 龙和王妃轮流从袋子里抓老鼠。谁先抓到白色老师谁就赢。 王妃每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。 每次抓老鼠和跑出来的老鼠都是随机的。 如果两个人都没有抓到白色老鼠则龙赢。王妃先抓。 问王妃赢的概率。 思路： 设dp[i][j]表示现在轮到王妃抓时有i只白鼠，j只黑鼠，王妃赢的概率 明显 dp[0][j]=0,0<=j<=b;因为没有白色老鼠了       dp[i][0]=1,1<=i<=w;因为都是白色老鼠，抓一次肯定赢了。       dp[i][j]可以转化成下列四种状态：       1、王妃抓到一只白鼠，则王妃赢了，概率为i/(i+j);       2、王妃抓到一只黑鼠，龙抓到一只白色，则王妃输了，概率为j/(i+j)*i/(i+j-1).       3、王妃抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，则转移到dp[i][j-3]。       概率为j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2);       4、王妃抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，则转移到dp[i-1][j-2].       概率为j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2);

当然后面两种情况要保证合法，即第三种情况要至少3只黑鼠，第四种情况要至少2只白鼠

#include #include #include #include using namespace std;const int maxn = 1010;int w, b;double dp[maxn][maxn];int main() { scanf("%d%d", &w, &b); for (int i = 0; i <= b; i++) dp[0][i] = 0; for (int i = 1; i <= w; i++) dp[i][0] = 1; for (int i = 1; i <= w; i++) { for (int j = 1; j <= b; j++) { dp[i][j] = 1.0*i/(i+j); if (j >= 2) dp[i][j] += 1.0*j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2]; if (j >= 3) dp[i][j] += 1.0*j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3]; } } printf("%.9f\n", dp[w][b]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。