Light OJ 1050 - Marbles（概率DP）

题目大意：

一个包裹里有蓝色和红色的弹珠，在这个包裹里有奇数个弹珠，你先走，你先从背包里随机的拿走一个弹珠，拿走每个弹珠的可能性是一样的。然后Jim从背包里拿走一个蓝色的弹珠，如果没有蓝色的弹珠让Jim拿走，那么Jim赢，如果最终从包裹里移走的是蓝的弹珠，那么你赢，否则Jim赢。给你蓝色和红的背包的里弹珠的个数，求赢的概率。

dp[R][B] 代表 R个红球， B个白球的时候赢得概率。当遇到 (R+B)%2 == 0 得时候直接 dp[R][B] = dp[R][B-1]就OK了。

这里采用的是记忆化搜索，所以用起来比较方便。

==============================================================================================================

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

const int INF = 1e9+;

const int MAXN = ;

double dp[MAXN][MAXN];

double DFS(int R,int B)

{

    if(dp[R][B] != -)

        return dp[R][B];

    if(R >= B || B == )

        return dp[R][B] = ;

    if(R == )

        return dp[R][B] = ;

    double k = 1.0/(R + B);

    if( (R+B)% )

        dp[R][B] =  1.0*R*k*DFS(R-,B) + 1.0*B*k*DFS(R, B-);

    else

        dp[R][B] = DFS(R, B-);

    return dp[R][B];

}

int main()

{

    int T, cas = , n, R, B;

    for(int i=; i<=; i++)

    for(int j=; j<=; j++)

    dp[i][j] = dp[i][j] = -;

    scanf("%d", &T);

    while(T --)

    {

        scanf("%d %d", &R, &B);

        printf("Case %d: %.9lf\n",cas ++, DFS(R, B) );

    }

    return ;

}

巴特西

Light OJ 1050 - Marbles（概率DP）

最新文章

热门文章