题目大意:桌面上有 R 张红牌和 B 张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到 1 美元，黑牌则付出 1 美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
考虑期望Dp
设\(f[a][b]\)表示有a张红牌，b张黑牌时的期望钱数
容易得到\(f[a][0]=a\)
\(f[a][b]\)可以从两个状态转移过来，即\(f[a-1][b]\)和\(f[a][b-1]\)
从\(f[a-1][b]\)的概率为\(\frac{a}{a+b}\)，转移过来期望加1
从\(f[a][b-1]\)的概率为\(\frac{b}{a+b}\)，转移过来期望减1
然后就可以得到\(f[a][b]=(f[a-1][b]+1)\times \frac{a}{a+b}+(f[a][b-1]-1)\times \frac{b}{a+b}\)
但是在\(b>a\)时，\(f[a][b]\)是负数，它真的是负数吗？
不是，因为根据最优策略\(f[a][b]\)可以等于0
所以\(f[a][b]=max(0,(f[a-1][b]+1)\times \frac{a}{a+b}+(f[a][b-1]-1)\times \frac{b}{a+b})\)
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int s=1,a=0;
char c=getchar();
while(!isdigit(c)) {
if(c==‘-‘) s=-s;
c=getchar();
}
while(isdigit(c)) {
a=a*10+c-‘0‘;
c=getchar();
}
return s*a;
}
const int N=5e3+8;
int r,b;
double f[2][N];
int main() {
r=read(),b=read();
for(int i=1;i<=r;i++) {
f[i&1][0]=i*1.0000000;
for(int j=1;j<=b;j++) {
f[i&1][j]=max(0.0000000,(f[i&1^1][j]+1)*((i*1.0000000)/(i+j)*1.0000000)+(f[i&1][j-1]-1)*((j*1.0000000)/(i+j)*1.0000000));
}
}
f[r&1][b]-=0.0000005;
printf("%.6f\n",f[r&1][b]);
return 0;
}