bzoj1419 Red is good

Red is good

Time Limit: 10 Sec Memory Limit: 64 MB

Description

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

Input

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

Output

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

Sample Input

5 1

Sample Output

4.166666

HINT

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

这道题，空间，滚动数组。
最优策略：如果当前局面的期望为负，则直接停止。（你玩个游戏就人脑dp？？那你还用玩这个？？）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 5;
double dp[3][maxn];
int R, B;

int main()
{
	scanf("%d%d", &R, &B);
	for(int i = 1; i <= R; ++i)
	{
		int t = i % 2; dp[t][0] = i;
		for(int j = 1; j <= B; ++j)
			dp[t][j] = max(0.0, (dp[t][j - 1] - 1) * ((double)(j) / (i + j)) + (dp[t ^ 1][j] + 1) * ((double)(i) / (i + j)));
	}
	printf("%.6lf
", dp[R % 2][B] - 0.0000005);
	return 0;
}