【题意】
R红B蓝,选红得1选蓝失1,问最优状态下的期望得分。
【思路】
设f[i][j]为i个Rj个B时的最优期望得分,则有转移式为:
f[i][j]=max{ 0,(f[i-1][j]+1)*(i/(i+j))+(f[i][j-1]-1)*(j/(i+j)) }
有i/(i+j)的可能性得1分,有j/(i+j)的可能性失1分,再加上原来的分数,则期望得分为上式。
需要用下滚动数组。直接按位数输出采用的四舍五入的方法,所以还需要减去5e-7。
【代码】
#include<cstdio>
#include<iostream>
using namespace std; const int N = 5e3+; int cur,R,B;
double f[][N]; int main()
{
scanf("%d%d",&R,&B);
for(int i=;i<=R;i++) {
cur^=;
f[cur][]=i;
for(int j=;j<=B;j++)
f[cur][j]=max((double),(+f[cur^][j])*((double)i/(i+j))+(-+f[cur][j-])*((double)j/(i+j)));
}
printf("%.6f",f[cur][B]-5e-);
return ;
}