BZOJ 1419: Red is good

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
",tmp%(long long)1e6);
    return 0;
}