题头

描述

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

输入

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

输出

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

样例输入

5 1

样例输出

4.166666

提示

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

又是一道概率dp

发现内存不够，只能用滚动数组优化，因为每一个状态只和他前一个状态有关

设dp[i][j]表示还剩i个red，j个black时的期望值

然后每一轮判断当前期望是正是负

如果是负了的话肯定是不能选的

注意顺带要判断这一轮要不要再翻牌

还有记住不要四舍五入

#include
    
     using namespace std;double dp[2][5005];int r,b;int main(){	cin>>r>>b;	int tmp=1;	for(int i=1;i<=r;i++)	{		dp[tmp][0]=i;		for(int j=1;j<=b;j++)		{			dp[tmp][j]=max(0.0,1.0*i/(i+j)*(dp[tmp^1][j]+1)+1.0*j/(i+j)*(dp[tmp][j-1]-1));		}		tmp^=1;	} 	printf("%0.6lf",dp[tmp^1][b]-0.0000005);	return 0;}