Bag of mice(概率dp)

https://www.luogu.com.cn/problem/CF148D

思路：

概率dp，设f[a][b]为白鼠为a个，黑鼠为b个时，赢的期望。

f[i][0]=1;

1.当先手取到白鼠时 a/(a+b);

2.当先手未取到白鼠，先手要向赢，后手也不能取到白鼠，跑掉的那一只随意

2.1 b/(a+b)*(b-1)/(a+b-1)*a/(a+b-2);

2.2 b/(a+b)*(b-1)/(a+b-1)*(b-2)/(a+b-2);

注意数据范围；

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int N=1e5+100;
const int MAX=1e9;
double f[1100][1100];
int w,k; 
int main(){
 cin>>w>>k;
 for(int i=1;i<=w;i++) f[i][0]=1;
 for(int  a=1;a<=w;a++)
 for(int b=1;b<=k;b++){
     f[a][b]=1.0*a/(a+b);
     if(a>=1&&b>=2)
     f[a][b]+=1.0*b/(a+b)*(b-1)/(a+b-1)*a/(a+b-2)*f[a-1][b-2];
    if(b>=3)
    f[a][b]+=1.0*b/(a+b)*(b-1)/(a+b-1)*(b-2)/(a+b-2)*f[a][b-3];
 }
 printf("%.9lf\n",f[w][k]);
    return 0;
}