乒乓球网站建设目标,科技布,手机版企业网站h5,188旅游网站源码下载CF 148 D. Bag of mice(概率dp求概率)
Problem - 148D - Codeforces
大意#xff1a;袋子里有 w 只白鼠和 b 只黑鼠 #xff0c;A和B轮流从袋子里抓#xff0c;谁先抓到白色谁就赢。A每次随机抓一只#xff0c;B每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人…CF 148 D. Bag of mice(概率dp求概率)
Problem - 148D - Codeforces
大意袋子里有 w 只白鼠和 b 只黑鼠 A和B轮流从袋子里抓谁先抓到白色谁就赢。A每次随机抓一只B每次随机抓完一只之后会有另一只随机老鼠跑出来。如果两个人都没有抓到白色则B赢。A先抓问A赢的概率。
思路看到数据范围后考虑 概率dp 设 dp[i][j] 为有 i 个白鼠 j 个黑鼠 A先手获胜的概率
考虑初始化
i 0 全是黑鼠 A 必败
dp[i][j] 0
j 0 全是白鼠 , A 必胜
dp[i][j] 1分情况考虑转移
分四种情况
1. A 取到白鼠 dp[i][j] i / (i j)
2. A 取到黑鼠 B取到白鼠 dp[i][j] 0;
3. A 取到黑鼠 B取到黑鼠 白鼠跑出来 dp[i][j] j / (i j) * (j - 1) / (i j - 1) * i / (i j - 2) * dp[i - 1][j - 2]
4. A 取到黑鼠 B取到黑鼠 黑鼠跑出来 dp[i][j] j / (i j) * (j - 1) / (i j - 1) * (j - 2) / (i j - 2) * dp[i][j - 3]#includebits/stdc.h
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N 1e3 10;
const int mod 1e9 7;
typedef pairint,intPII;double dp[N][N];
int x , y;inline double pro(int x , int y){return (double) x / (double) y;
}signed main(){IOScout fixed setprecision(10);cin x y;for(int i 1 ; i x ; i ) dp[i][0] 1;for(int i 1 ; i y ; i ) dp[0][i] 0;for(int i 1 ; i x ; i ){for(int j 1 ; j y ; j ){dp[i][j] pro(i , i j);if(i 1 j 2) dp[i][j] pro(j , i j) * pro(j - 1 , i j - 1) * pro(i , i j - 2) * dp[i - 1][j - 2];if(j 3) dp[i][j] pro(j , i j) * pro(j - 1 , i j - 1) * pro(j - 2 , i j - 2) * dp[i][j - 3];}}cout dp[x][y];return 0;
}
//freopen(文件名.in,r,stdin);
//freopen(文件名.out,w,stdout);
