CF 148D Bag of mice （概率DP）

淩亂°似流年 2021-11-01 03:42 225阅读 0赞

题目链接：http://codeforces.com/problemset/problem/148/D

题意：袋子里有w只白鼠和b只黑鼠，由公主开始，公主和龙轮流从袋子中抓一只老鼠，先抓到白鼠的赢。特别的：龙每次抓完老鼠会有一只老鼠跑出来。

每次抓老鼠和跑出来的老鼠都是随机的。如果两个人都没有抓到白色老鼠则龙赢。求公主赢的概率。

思路：dp\[i\]\[j\]表示轮到公主抓时袋子里还剩i只白鼠j只黑鼠时公主赢的概率。

初始化：dp\[0\]\[j\]=0,0<=j<=b; dp\[i\]\[0\]=1,1<=i<=w;

dp\[i\]\[j\]有4种转移情况：

公主抓到一只白鼠，获胜，概率为i/(i+j)；

公主抓到一只黑鼠，龙抓到一只白鼠，失败，概率为j/(i+j)\*i/(i+j-1)；

公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只黑鼠，概率为j/(i+j)\*(j-1)/(i+j-1)\*(j-2)/(i+j-2)\*dp\[i\]\[j-3\]；

公主抓到一只黑鼠，龙抓到一只黑鼠，跑出来一只白鼠，概率为j/(i+j)\*(j-1)/(i+j-1)\*i/(i+j-2)\*dp\[i-1\]\[j-2\]。

#include <cstdio>
    #include <cstring>
    
    double dp[1005][1005];
    
    int main ()
    {
    	int w,b,i;
    	scanf("%d%d",&w,&b);
    	memset(dp,0,sizeof(dp));
    	for (i=1;i<=w;i++)
    		dp[i][0]=1.0;
    	for (i=0;i<=b;i++)
    		dp[0][i]=0;
    	for (i=1;i<=w;i++)
    		for (int j=1;j<=b;j++)
    		{
    			dp[i][j]+=1.0*i/(i+j);   //公主抓到白的
    			if (j>=3)
    				dp[i][j]+=1.0*j/(i+j)*(j-1)/(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)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2];
    		}
    	printf("%.9lf\n",dp[w][b]);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，225人围观）

还没有评论，来说两句吧...

相关阅读

相关【DP】CF1096D Easy Problem

题意：现在有一个由小写字母组成的[字符串][Link 1]，去掉这个字符串的第i个位置的字符会有ai的代价。你的任务是去掉这个字符串中的一些字符使得该字符串中不包含子序列h

比眉伴天荒/ 2024年03月26日 20:33/ 0 赞/ 87 阅读

相关【状压+概率DP】CF678 E

[Problem - E - Codeforces][] 题意： ![460fa11fa21742e4873f90d5cd114ad9.png][] 思路：首先，n

绝地灬酷狼/ 2024年03月24日 23:46/ 0 赞/ 81 阅读

相关【*1900 DP+Tree】CF9D

[Problem - 9D - Codeforces][] 题意： ![08c35e73a5d74fb1a152f832fd807c81.png][] 思路：计数问

落日映苍穹つ/ 2024年03月16日 10:29/ 0 赞/ 48 阅读

相关【计数DP】CF1794D

[Problem - D - Codeforces][] 题意 ![06493c1d861a49e6995818c716958851.png][] 思路解法大方向对了

痛定思痛。/ 2024年02月21日 12:04/ 0 赞/ 69 阅读

相关【换根DP】CF1882 D

[Problem - D - Codeforces][] ![deb798f4239b42af8fc9c94f32fdb2aa.png][] 思路：一个很套路的换根

Bertha 。/ 2024年02月21日 03:15/ 0 赞/ 95 阅读

相关【数位DP】CF55D Beautiful numbers

$dp\[x\]\[p\]\[pp\]$表示第x位，当前已有数字mod 2520（1~9数字的lcm）为p，当前各位数字的lcm为pp 观察到数组太大，考虑压缩，第三维lcm

矫情吗；*/ 2023年06月01日 06:10/ 0 赞/ 19 阅读

相关 codeforces 148D Bag of mice (概率)

The dragon and the princess are arguing about what to do on the New Year's Eve. The drag

r囧r小猫/ 2022年06月04日 06:48/ 0 赞/ 121 阅读

相关浅析Bag-of-words及Bag-of-features

目录 Bag-of-words简介 Bag-of-words应用于图像 Bag-of-features基础流程 1、特征提取 2、学习 “视觉词典（visual vo

缺乏、安全感/ 2022年02月04日 17:51/ 0 赞/ 244 阅读

相关线性dp——cf1096D

dp\[i\]\[j\]表示到第i位，与hard的匹配状态到达了第j位每位有两种决策：消或者不消分别转移一下即可转移代码 for(register int

忘是亡心i/ 2021年11月19日 15:06/ 0 赞/ 263 阅读

相关 CF 148D Bag of mice （概率DP）

题目链接：http://codeforces.com/problemset/problem/148/D 题意：袋子里有w只白鼠和b只黑鼠，由公主开始，公主和龙轮流从袋子中抓一

淩亂°似流年/ 2021年11月01日 03:42/ 0 赞/ 226 阅读