Red is good

期望概率DP

1419: Red is good

Description

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

Input

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

Output

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

Sample Input

5 1

Sample Output

4.166666

HINT

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

solution

这是我做的第一道期望概率DP题，刚刚看题时有点蒙。听完讲解之后感觉还是挺简单的。

我们用\(f[i][j]\)表示翻了\(i\)张红牌，翻了\(j\)张黑牌的最优期望值。

考虑怎么预处理。当全部是红牌时，最优策略肯定是\(i\)，即\(f[i][0] = 1\)；当全部是黑牌时，还不如不翻牌，最优策略就是0，即\(f[0][i] = 0\)。

再考虑怎么转移。\(f[i][j] = max(0, \frac{i}{i+j}*(f[i - 1][j] + 1) + \frac{j}{i+j}*(f[i][j - 1] - 1)\)；每翻一张红牌的概率是\(\frac{i}{i+j}\)，它的权值是\(f[i - 1][j] + 1\)。黑牌同理。

由于这道题的空间限制是\(64MB\)，所以要用到滚动数组。我们更新当前状态时只与上一次有关，将第一维开2的大小就好了。

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 5001;
int n, m;
double f[3][N];

double max(double a, double b) {
	if(a >= b) return a;
	return b;
}

int main() {
	
	freopen("e.in","r",stdin);
	freopen("e.out","w",stdout);
	
	cin >> n >> m;
	for(int i = 1;i <= n; i++) {
		f[i % 2][0] = i;
		for(int j = 1;j <= m; j++) {
			f[i % 2][j] = max(0, ((double)i/(i + j) * (f[(i - 1) % 2][j] + 1)) + ((double)j/(i + j) * (f[i % 2][j - 1] - 1)));
		}
	}
	
	printf("%.6f", f[n % 2][m] - 0.0000005); //小数点第六位后面的都去掉
	
	fclose(stdin); fclose(stdout);
	return 0;	
}