Red is good

题目描述

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

输入

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

输出

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

solution

f[i][j]表示当前拿i个红球，j个黑球时的期望钱数

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

f[i][0]=i

由于内存，开滚动数组

(一开始想反着定义来着)

#include<cstdio>
#include<cstring>
#include<iostream>
#define dd double
using namespace std;

int R,B,now;
dd f[2][5066];

int main(){
    
    scanf("%d%d",&R,&B);
    
    now=0;
    dd temp;
    for(int i=1;i<=R;++i)
    {
        now^=1;
        f[now][0]=i;
        for(int j=1;j<=B;++j)
        {
            temp=(f[now][j-1]-1)*(dd)(j)/(dd)(i+j)+(f[now^1][j]+1)*(dd)(i)/(dd)(i+j);
          f[now][j]=temp>0?temp:0;
        }
    }
    printf("%.6lf",f[now][B]-0.0000005);
    
    //while(1);
}