题目链接：http://codeforces.com/problemset/problem/148/D
题意：
原来袋子里有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仅仅白鼠
by 点击打开链接
#include "stdio.h" #include "math.h" #include <iostream>清理Word代码 using namespace std; const int N = 1005; int w, b; double dp[N][N];//dp[i][j]表示i仅仅白 j仅仅黑 double solve(){ for(int i = 0; i <= w; i++) dp[i][0] = 1; for(int i = 0; i <= b; i++) dp[0][i] = 0; dp[0][0] = 0; for(int ii = 1; ii <= w; ii++) for(int jj = 1; jj <= b; jj++) { double i = ii, j = jj; dp[ii][jj] = i / (i+j); if(j-3>=0) dp[ii][jj] += dp[ii][jj-3] * j / (i+j) * (j-1) / (i+j-1) * (j-2) / (i+j-2); if(j>=2 &&i>=1) dp[ii][jj] += dp[ii-1][jj-2] * j / (i+j) * (j-1) / (i+j-1) * i / (i+j-2); } return dp[w][b]; } int main (){ while(cin>>w>>b){ printf("%.10f\n", solve()); } return 0; }
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5229597.html，如需转载请自行联系原作者
