输出答案时,小数点后第六位后的全部去掉,不要四舍五入.
概率期望DP
$f[i][j]$表示选$i$张红和$j$张黑的答案
转移就是期望*概率
$f[i][j]=max(0,\frac{i}{i+j}*(f[i-1][j]+1)+\frac{j}{i+j}*(f[i][j-1]-1))$
卡内存需要滚动数组
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int R,B,now; double f[2][5001]; int main() { scanf("%d%d",&R,&B); for (int i=0; i<=R; i++,now^=1,f[now][0]=i) for (int j=1; j<=B; j++) f[now][j]=max(0*1.0,1.0*i/(i+j)*(f[now^1][j]+1)+1.0*j/(i+j)*(f[now][j-1]-1)); long long ans=f[R&1][B]*1000000; printf("%lf",(double)ans/1000000); return 0; }
原文：http://www.cnblogs.com/DaD3zZ-Beyonder/p/5902459.html