摘要：
你每小时都随机从箱子里面抽出两个小球，然后把这两个球都染成黑球，然后再放回去。问需要多少小时才能把所有小球变成黑色小球？则$f[i][j]=*...+*...+f[i][j]...+1*...$移项得$f[i][j]=...+*...+1*...$(...)的部分请自行思考总结：理清思路，一个正推反推调了两天。据@info___tion，很多时候期望DP是往后推的（？
题意：一个箱子里面有n个黑球m个白球。你每小时都随机从箱子里面抽出两个小球，然后把这两个球都染成黑球，然后再放回去。问需要多少小时才能把所有小球变成黑色小球？输出期望值。
题解：
期望DP
设(f[i][j])是到达(i)黑球与(j)白球的期望。
则$ f[i][j]=(f[i-1][j+1] +1)* ... + (f[i-2][j+2]+1)*...+f[i][j] ...+ 1 *... $
移项得$ f[i][j](1-...)=(f[i-1][j+1] +1) ... + (f[i-2][j+2]+1)*...+ 1 *... $
(f[i][j]=frac{(f[i-1][j+1] +1)* ... + (f[i-2][j+2]+1)*...+ 1 *... }{1-...})
(...)的部分请自行思考
总结：
理清思路，一个正推反推调了两天。
据@info___tion，很多时候期望DP是往后（结果往起点）推的（？
代码
#include<bits/stdc++.h>
using namespace std;
int t,n,m;double f[100][100];bool vis[100][100];
void dfs(int i,int j)
{
if (i>=n+m&&j<=0) return ;
if (vis[i][j]) return ;
vis[i][j]=true;
dfs(i+1,j-1);
dfs(i+2,j-2);
if (j-1>=0) f[i][j]=(f[i+1][j-1]+1.0)*((j*1.0)/(n+m) * (i*1.0)/(n+m-1.0)
+ (i*1.0)/(n+m) * (j*1.0)/(n+m-1.0)) ;
if (j-2>=0) f[i][j]+=(f[i+2][j-2]+1.0)* (j*1.0)/(n+m)*(j-1.0)/(n+m-1.0);
f[i][j]=(f[i][j] )/ (1.0-1.0* i/(n+m)*(i-1.0)/(n+m-1))+(1.0*i*1.0/(n+m)*(i-1.0)/(n+m-1.0))/(1.0-i*1.0/(n+m)*(i-1.0)/(n+m-1.0));
}
int main()
{
freopen("2829.in","r",stdin);
freopen("2829.out","w",stdout);
cin>>t;
for (int tt=1;tt<=t;tt++)
{
cin>>n>>m;
for (int i=0;i<=n+m;i++)
for (int j=0;j<=m;j++)
f[i][j]=0,vis[i][j]=0;
dfs(n,m);
printf("%.8lf
",f[n][m]) ;
}
return 0;
}