首页 > 代码库 > CF 148D(概率dp)

CF 148D(概率dp)

2024-11-24 12:10:39   203人阅读

 

题目连接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26308

题意：原来袋子里有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 <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;double dp[1010][1010];int main(){    int w,b;    while(scanf("%d%d",&w,&b)>0)    {        FILL(dp,0);        for(int i=0;i<=b;i++)dp[0][i]=0;        for(int i=1;i<=w;i++)dp[i][0]=1;        for(int i=1;i<=w;i++)            for(int j=1;j<=b;j++)        {            dp[i][j]+=i*1.0/(i+j);            if(j>=3)                dp[i][j]+=1.0*j/(i+j)*(j-1)*1.0/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];            if(j>=2)                dp[i][j]+=1.0*j/(i+j)*(j-1)*1.0/(i+j-1)*(i)/(i+j-2)*dp[i-1][j-2];        }        printf("%.9lf\n",dp[w][b]);    }}
View Code

 

CF 148D(概率dp)


联系
我们