Red is good

Description

桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付

出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。

Input

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

Output

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

解析

设计状态：\(f[i][j]\) 表示在 \(i\) 张红，\(j\) 张黑中选的期望得分。

此时抽到一张红的概率为 \(\frac{i}{i+j}\)，抽到一张黑的概率为 \(\frac{j]{i+j}\)。

再加上之后 \(f[i-1][j]\) 或 \(f[i][j-1]\) 的期望就好啦。

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int r,b;
double f[N][N],ans;

int main()
{
	scanf("%d%d",&r,&b);
	for(int i=1;i<=r;i++)
	{
		f[i][0]=i;
		for(int j=1;j<=b;j++)
			f[i][j]=max(0.0,(f[i-1][j]+1)*i/(i+j)+(f[i][j-1]-1)*j/(i+j));
	}
	printf("%.6lf\n",f[r][b]-0.0000005);
	return 0;
}

优化

卡空间，我们发现状态转移只涉及两个位置，即 \((i-1,j)\) 和 \((i,j-1)\)。

也就是当前这一阶段的上一个位置和上一个阶段的当前位置。

而遍历到当前位置时这一阶段的上一个位置已经被更新过了，这个位置还是上一个阶段的。而这刚好是我们要的。

因此二维数组可以压成一维。

#include<bits/stdc++.h>
using namespace std;
const int N = 5001;
int r,b;
double f[N];

int main()
{
	scanf("%d%d",&r,&b);
	for(int i=1;i<=r;i++)
	{
		f[0]=i;
		for(int j=1;j<=b;j++)
			f[j]=max(0.0,(f[j]+1)*i/(i+j)+(f[j-1]-1)*j/(i+j));
	}
	printf("%.6lf\n",f[b]-0.0000005);
	return 0;
}