【BZOJ 1419】Red is good期望dp

设f[i][j]表示还剩i张红牌，j张黑牌的期望得分，不难写出方程

f[i][j]=max(0,(f[i-1][j]+1)*i/(i+j)+(f[i][j-1]-1)*j/(i+j));

然后。。居然mle就只好滚动咯

#include<cstdio> #include<cstring> #include<iostream> #define maxn 5021 using namespace std; double f[2][maxn]; int n,m; int main(){ scanf("%d%d",&n,&m); int pos=0; for(int i=1;i<=n;i++){ pos^=1;memset(f[pos],0,sizeof(f[pos])); for(int j=0;j<=m;j++){ if(!j)f[pos][j]=i*1.0; else f[pos][j]=max(0.0,(f[pos^1][j]+1.0)*i*1.0/(i+j)+(f[pos][j-1]-1.0)*j*1.0/(i+j)); } } printf("%.6lf",f[pos][m]-5e-7); return 0; }