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\n",tmp%(long long)1e6);

    return 0;

}

巴特西

BZOJ 1419: Red is good

Sol

Code

最新文章

热门文章