设$dp[i][j]$为有i张红j张黑时的期望最大值
因为随时可以停止所以当期望小于0时直接改成0
同时因为会爆空间所以改成滚动数组
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5005;
int R,B;
double dp[2][N];
inline void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
int main(){
freopen("1419.in","r",stdin);
freopen("1419.out","w",stdout);
Read(R);Read(B);
for(register int i=1;i<=R;i++){
int now=i&1,pre=now^1;
dp[now][0]=i;
for(register int j=1;j<=B;j++){
double Px=1.0*i/(i+j);
dp[now][j]=Px*(dp[pre][j]+1)+(1-Px)*(dp[now][j-1]-1);
if(dp[now][j]<0)dp[now][j]=0;
}
}
printf("%.6lf\n",dp[R&1][B]-0.0000005);
return 0;
}
评论 (0)
