概率dp
设 f(i,j)f(i,j) 表示有 ii 只白鼠，jj 只黑鼠时A先手胜的概率
初始状态
全白时，显然先手必胜
有一只黑鼠时，先手若抽到黑鼠则后手必胜，所以先手首回合必须抽到白鼠
f(i,0)=1,f(i,1)=\frac{i}{i+1}f(i,0)=1,f(i,1)=i+1i
转移方程 f(i,j)f(i,j)
先手抽到白鼠，胜：\frac{i}{i+j}i+ji
先手抽到黑鼠，后手抽到白鼠，败： 00
先手抽到黑鼠，后手抽到黑鼠，跑一只白鼠：\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{i}{i+j-2}\times f(i-1,j-2)i+jj×i+j−1j−1×i+j−2i×f(i−1,j−2)
先手抽到黑鼠，后手抽到黑鼠，跑一只黑鼠：\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{j-2}{i+j-2}\times f(i,j-3)i+jj×i+j−1j−1×i+j−2j−2×f(i,j−3)
f(i,j)=\frac{i}{i+j}+\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{i}{i+j-2}\times f(i-1,j-2)+\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{j-2}{i+j-2}\times f(i,j-3)f(i,j)=i+ji+i+jj×i+j−1j−1×i+j−2i×f(i−1,j−2)+i+jj×i+j−1j−1×i+j−2j−2×f(i,j−3)
O(wb)O(wb)
1 #include<bits/stdc++.h> 2 using namespace std; 3 inline int read() 4 { 5 int N=0,C=0;char tf=getchar(); 6 for(;!isdigit(tf);tf=getchar())C|=tf=='-'; 7 for(;isdigit(tf);tf=getchar())N=(N<<1)+(N<<3)+(tf^48); 8 return C?-N:N; 9 } 10 const int N=1010; 11 int w,b; 12 double f[N][N]; 13 int main() 14 { 15 w=read(),b=read(); 16 for(int i=1;i<=w;++i) 17 f[i][0]=1.0,f[i][1]=1.0*i/(i+1); //全白必胜，一黑首回合必须抽到白鼠 18 if(!b||b==1) return printf("%.9lf\n",f[w][b]),0; 19 for(int i=1;i<=w;++i) 20 for(int j=2;j<=b;++j){ 21 f[i][j]=1.0*i/(i+j); 22 f[i][j]+=1.0*j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*f[i-1][j-2];//跑白 23 //自我感觉这里可以改成j>=3; 24 //不过没验证过 25 if(j^2) f[i][j]+=1.0*j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*f[i][j-3];//跑黑 26 } 27 printf("%.9lf\n",f[w][b]); 28 29 return 0; 30 }