暑假集训 || 概率DP

Codeforces 148D

考虑状态转移。。https://www.cnblogs.com/kuangbin/archive/2012/10/04/2711184.html
题意：原来袋子里有w只白鼠和b只黑鼠，龙和王妃轮流从袋子里抓老鼠，谁先抓到白色老鼠谁就赢
王妃每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。
王妃先抓，如果两个人都没有抓到白色老鼠则龙赢，问王妃赢的概率

思路：设dp[i][j]表示现在轮到王妃抓时有i只白鼠，j只黑鼠，王妃赢的概率

明显 dp[0][j]=0,0<=j<=b;因为没有白色老鼠了
dp[i][0]=1,1<=i<=w;因为都是白色老鼠，抓一次肯定赢了。
dp[i][j]可以转化成下列四种状态：
1、王妃抓到一只白鼠，则王妃赢了，概率为i/(i+j);
2、王妃抓到一只黑鼠，龙抓到一只白色，则王妃输了，概率为j/(i+j)*i/(i+j-1).
3、王妃抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，则转移到dp[i][j-3]，概率为j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2);
4、王妃抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，则转移到dp[i-1][j-2]，概率为j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2);

当然后面两种情况要保证合法，即第三种情况要至少3只黑鼠，第四种情况要至少2只白鼠

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <queue>

#include <algorithm>

using namespace std;

const int SZ = ;

double f[SZ][SZ];

//white->i->win black->j

int main()

{

    int w, b;

    scanf("%d %d", &w, &b);

    for(int i = ; i <= w; i++) f[i][] = ;

    for(double i = ; i <= w; i++)

        for(double j = ; j <= b; j++)

        {

            int ii = (int)i, jj = (int)j;

            f[ii][jj] += i / (i + j);//w

            if(j >= ) f[ii][jj] += j/(i+j) * (j-)/(i+j-) * i/(i+j-) * f[ii-][jj-];//bb->w

            if(j >= ) f[ii][jj] += j/(i+j) * (j-)/(i+j-) * (j-)/(i+j-) * f[ii][jj-];//bb->b

        }

    printf("%.9f\n", f[w][b]);

    return ;

}

巴特西

暑假集训 || 概率DP

最新文章

热门文章