题目描述

Description

桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。

Input

一行输入两个数R,B,其值在0到5000之间

Output

在最优策略下平均能得到多少钱。

Sample Input

5 1

Sample Output

4.166666

HINT

输出答案时,小数点后第六位后的全部去掉,不要四舍五入.

题目分析

$f[i][j]$表示还剩$i$张红牌,$j$张黑牌时在最优策略下得到的钱

初始化:$f[i][0]=i$

$f[i][j]=max(0,(f[i-1][j]+1)* \frac{i}{i+j}+(f[i][j-1]-1)*\frac{j}{i+j})$
最后由于空间开不下 我们使用滚动数组黑科技

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
double f[2][5010];
int main()
{
    scanf("%d%d",&n,&m);
    int k=0;
    for(int i=1;i<=n;i++)
    {
        k^=1;
        f[k][0]=i;
        for(int j=1;j<=m;j++)
        {
            double tmp=i;
            tmp/=(double)(i+j);
            double nmp=j;
            nmp/=(double)(i+j);
            f[k][j]=max(0.0,(f[k^1][j]+1)*tmp+(f[k][j-1]-1)*nmp);
        }
    }
    double x=floor(f[k][m]*1000000);  
    x/=1000000;  
    printf("%.6lf\n",x); 
    return 0;
}