问题 J: Red is good
时间限制: 1 Sec 内存限制: 64 MB题目描述
桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
输入
一行输入两个数R,B,其值在0到5000之间
输出
在最优策略下平均能得到多少钱。
样例输入
5 1
样例输出
4.166666
提示
输出答案时,小数点后第六位后的全部去掉,不要四舍五入.
f[i][j] 还剩i张红 j张黑可得最大价值
i==0 0
j==0 i
else f[i][j]=max(0,i/(i+j)*(1+f[i-1][j])+j/(i+j)*(-1+f[i][j-1]));
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#include<cstdlib>
#include<algorithm>
#define V 5090
#define LL long long
using namespace std;
double f[2][V];
int n,m;
inline int haha()
{//freopen("in.txt","r",stdin);cin>>n>>m;double x,y;int num=0;for(int i=0;i<=n;i++){num^=1;for(int j=0;j<=m;j++){if(i==0){f[num][j]=0;continue; }if(j==0){f[num][j]=i;continue;}x=i;y=j;f[num][j]=max(0.0,x/(x+y)*(1+f[num^1][j])+y/(x+y)*(-1+f[num][j-1]));}}double xx=0.0000005;f[num][m]-=xx;printf("%.6lf",f[num][m]);//cout<<f[n][m];return 0;
}
int gg=haha();
int main()
{;}