http://codeforces.com/problemset/problem/148/D (题目链接)
题意
包中有w个白鼠,b个黑鼠。公主和龙轮流画老鼠,公主先画,谁先画到白鼠谁就赢。龙每画完一只老鼠,就会有另一只老鼠从包中跑出来。每只老鼠被画到以及跑出的概率相等,问公主获胜的概率。
Solution
令${f_{0/1,i,j}}$表示此时公主/龙选,包中还剩i只白鼠,j只黑鼠,公主赢的概率。那么转移很显然:
$${f_{0,i,j}=\frac{i}{i+j}+\frac{j}{i+j}*f_{1,i,j-1}}$$
$${f_{1,i,j}=\frac{j}{i+j}*(\frac{i}{i+j-1}*f_{0,i-1,j-1}+\frac{j}{i+j-1}*f_{0,i,j-2})}$$
细节
一个加号没打,看半天没看出来。。
代码
// codeforces148D #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define inf 1<<30 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std; const int maxn=1010; double f[2][maxn][maxn]; int n,m; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) f[0][i][0]=1; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { f[0][i][j]=(double)(i+j*f[1][i][j-1])/(i+j); f[1][i][j]=(double)(i*f[0][i-1][j-1])/(i+j-1); if (j>1) f[1][i][j]+=(double)((j-1)*f[0][i][j-2])/(i+j-1); f[1][i][j]*=(double)j/(i+j); } printf("%.9lf",f[0][n][m]); return 0; }