BZOJ 1419 Red is good

题目大意

给你一些牌，这些牌只有两种：红牌和黑牌，抽到红牌得一元，抽到黑牌扣一元，问使用最优策略最终期望得到的钱数。

初探概率期望……首先考虑正着推。设$F_{i,j}$是红牌剩余i张，黑牌剩余j张的期望收入，我们得到方程

$$F_{i,j} = \frac{i+1}{i+1+j}(F_{i+1,j}+1)+\frac{j+1}{i+j+1}(F_{i,j+1}-1)$$

但是这出现了一个问题：我们既然选择这样推那么就需要知道最大的，也就是初始F值。但是这就是我们要求的东西= =

怕是石乐志刚刚才想明白咋正确地反着推……设$F_{i,j}$是红牌剩余i张，黑牌剩余j张的期望收入，那么对于$F_{i+1,j}$也就是最先抽的这张是红色的情况就一定有这个东西是$F_{i,j}$加上收入而来的。原因是前者是上一个最终状态，推到新的最终状态的时候直接加上去就可以了，而不能和正着推放在一起讨论。

$$F_{i,j} = \frac{i}{i+j}(F_{i-1,j}+1)+\frac{j}{i+j}(F_{i,j-1}-1)$$

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int r,b,flg;
double f[2][5010];
int main()
{
	scanf("%d%d",&r,&b);
	for(int i=1;i<=r;++i)
	{
		flg=i%2;
		f[flg][0]=i;
		for(int j=1;j<=b;++j)
		{
			f[flg][j]=(1.0*(i)/(i+j))*(f[flg^1][j]+1)+(1.0*(j)/(i+j))*(f[flg][j-1]-1);
			if(f[flg][j]<0) f[flg][j]=0;
		}
	}
	printf("%.6lf",floor(f[r%2][b]*1000000)/1000000);
	return 0;
}