[文章目录]
Description
桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。两个数R,B,其值在0到5000之间
概率DP，dp[a][b]表示剩a张红牌，b张黑牌能得到钱的期望。如果期望值小于0，那么根据最优策略原则，认为概率为0.
转移：dp[a][b]=a/(a+b)*(dp[a-1][b]+1)+b/(a+b)*(dp[a][b-1]-1)
然后ans不四舍五入的话直接换成int然后除，注意不能数据溢出。
本来写了个记忆化搜索，结果这题卡空间MLE了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
double dp[2][5010];
int main()
{
scanf("%d%d",&n,&m);
bool flag=1;
for(int i=1;i<=n;++i)
{
dp[flag][0]=i;
for(int j=1;j<=m;++j)
{
dp[flag][j]=((double)i/(double)(i+j))*(dp[flag^1][j]+1.0)+((double)j/(double)(i+j))*(dp[flag][j-1]-1.0);
if(dp[flag][j]<0) dp[flag][j]=0;
}
flag^=1;
}
long long x=(dp[flag^1][m]*10000000);
x/=10;
double y=x*0.000001;
printf("%.6lf",y);
return 0;
}