输出答案时,小数点后第六位后的全部去掉,不要四舍五入.
概率期望DP
f[i][j]表示有i张红j张黑情况下的期望收益
f[i][j]=max(0,i/(i+j)*(f[i-1][j]+1)+j/(i+j)*(f[i][j-1]-1))
转移是和很好理解的，如果选了的期望收益<0，那么不如不选
ps:
1、滚动数组压内存
2、去尾，不是四舍五入
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int N=5005; int n,m; double f[2][N]; int main(){ scanf("%d%d",&n,&m); int now=0; for(int i=1;i<=n;i++){ now^=1; f[now][0]=i; for(int j=1;j<=m;j++){ f[now][j]=max(0.0,(f[now^1][j]+1)*i/(i+j)+(f[now][j-1]-1)*j/(i+j)); } } char ans[35]; sprintf(ans,"%.7lf",f[now][m]); int len=strlen(ans);ans[len-1]=0; puts(ans); return 0; }
原文：http://www.cnblogs.com/shenben/p/6513373.html