题意:
袋中有w白鼠,b黑鼠.
A - princess B - dragon
A,B轮流随机拿出一只, A先拿, B拿了一只之后会有一只鼠随机跑出.
先拿到一只白鼠的获胜.
问A获胜的概率.
思路:
概率DP.
要义是记忆化搜索. 因为概率是一回合一回合累加的, 询问后面的概率时, 会用到前面的概率.
dp记录的内容和问题有关, 这里只问A获胜的概率, 则dp[i][j]表示当袋中还有i只白鼠,j只黑鼠时, A获胜的概率.
首先考虑边界条件.
dp[i][0] = 1;
dp[0][j] = 0;
dp[i][j] =
(考虑所有可使A赢的情况)
@直接取到白鼠:
i / (i+j);
@A取到黑鼠. B取到黑鼠. 跑出一白鼠. 情况回溯到dp[i-1][j-2]
j / (i+j) * (j-1) / (i+j-1) * i / (i+j-2) * dp[i-1][j-2];
@A取到黑鼠. B取到黑鼠. 跑出一黑鼠. 情况回溯到dp[i][j-3]
j / (i+j) * (j-1) / (i+j-1) * (j-2) / (i+j-2) * dp[i][j-3];
这就是所有的情况了.
用一个循环就可以得到答案. 正着循环填表.
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1005; double dp[MAXN][MAXN]; int main() { int w,b; scanf("%d %d",&w,&b); memset(dp,0,sizeof(dp)); for(int i=1;i<=w;i++) dp[i][0] = 1.0; for(int i=1;i<=w;i++) for(int j=1;j<=b;j++) { dp[i][j] += (double)i / (i+j); if(i>=1 && j>=2) dp[i][j] += (double)j / (i+j) * (j-1) / (i+j-1) * i / (i+j-2) * dp[i-1][j-2]; if(j>=3) dp[i][j] += (double)j / (i+j) * (j-1) / (i+j-1) * (j-2) / (i+j-2) * dp[i][j-3]; } printf("%.9lf\n",dp[w][b]); }