Sol
期望DP.
\(f[i][j]\) 表示剩下 \(i\) 张红牌, \(j\) 张黑牌的期望.
有转移方程.
\(f[i][j]=0,i=0\) 没有红色牌了,最优方案就是不再翻了.
\(f[i][j]=i,j=0\) 只剩下红色牌了,那就全部翻完啊.
\(f[i][j]=max\{ 0,\frac{i}{i+j}(f[i-1][j]+1)+\frac{j}{i+j} (f[i][j-1]-1)\}\) 翻到红色的概率是 \(\frac{i}{i+j}\) ,翻到黑色的概率是 \(\frac{j}{i+j}\) ,并且要取个下界 \(0\) .
精度很吃屎.
Code
/**************************************************************
Problem: 1419
User: BeiYu
Language: C++
Result: Accepted
Time:1408 ms
Memory:1352 kb
****************************************************************/ #include<cstdio>
#include<iostream>
using namespace std;
#define N 5005
double f[2][N];int r,b,cur;long long tmp;
int main(){
scanf("%d%d",&r,&b);
for(int i=0;i<=r;i++){
for(int j=0;j<=b;j++){
if(!i) f[cur][j]=0;else if(!j) f[cur][j]=i;
else f[cur][j]=max(0.0,(i*(1+f[cur^1][j])+j*(-1+f[cur][j-1]))/(i+j));
}cur^=1;
}tmp=f[cur^1][b]*1e6;
printf("%lld.",(long long)f[cur^1][b]);printf("%06lld\n",tmp%(long long)1e6);
return 0;
}