Description：

$R$ 张红牌 $B$ 张黑牌，随机打乱顺序，翻到红牌得 $1$ 元，黑牌付出 $1$ 元。可以随时停止翻牌，在最优策略下平均能得到多少钱。

$0\leqslant R,B\leqslant 5000$

Solution：

设 $f[i][j]$ 表示有 $n$ 张红牌 $m$ 张黑牌能得到的期望获利，下一次有 $\frac i{i+j}$ 的可能性反到红， $\frac j{i+j}$ 的可能性反到黑，转移为 $f[i][j]=\max(0,\frac i{i+j}f[i-1][j]+\frac j{i+j}f[i][j-1])$ ，要求向下取整所以用了一些奇怪的做法。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 5010

double f[2][MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int cur = 0;

	for(int i = 0;i <= n;++i)

	{

		cur ^= 1;

		memset(f[cur],0,sizeof(f[cur]));

		for(int j = 0;j <= m;++j)

		{

			if(i >= 1)f[cur][j] += i / double(i + j) * (f[cur ^ 1][j] + 1);

			if(j >= 1)f[cur][j] += j / double(i + j) * (f[cur][j - 1] - 1);

			if(f[cur][j] < 0)f[cur][j] = 0;

		}

	}

	long long ans = floor(f[cur][m] * 1000000);

	printf("%lld.%06lld",ans / 1000000,ans % 1000000);

	return 0;

}