CF148D 概率dp

本文主要是介绍CF148D 概率dp，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目大意

袋子里有 w 只白鼠和 b 只黑鼠，公主和龙轮流从袋子里抓老鼠。谁先抓到白色老鼠谁就赢，如果袋子里没有老鼠了并且没有谁抓到白色老鼠，那么算龙赢。公主每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。每次抓的老鼠和跑出来的老鼠都是随机的。公主先抓。问公主赢的概率。

\(w,b \leq 10^3\)

思路

设\(f_{ij}\)表示轮到公主的时候，当前还剩\(i\)白鼠\(j\)黑鼠，能够获胜的概率。

初始化：

• \(f_{i,0}=1\) 随便抓一个都是赢
• \(f_{0,i} = 0\)没有老鼠了算龙赢

\[f_{i,j} = {i \over (i + j)} + \begin{cases} {j \over (i + j)} * {(j - 1) \over (i + j - 1)} * {(j - 2) \over (i + j - 2)} * f_{i,j - 3} & 公主黑，龙黑，跑出黑 \\ {j \over (i + j)} * {(j - 1) \over (i + j - 1)} * {i \over (i + j - 2)} * f_{i - 1,j - 2} & 公主黑，龙黑，跑出白 \end{cases} \]

注意细节即可

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
double f[N][N];
int w,b;
int main () {
	cin >> w >> b;
	for(int i = 1;i <= w; i ++) {
		f[i][0] = 1;
	}
	for(int i = 1;i <= b;i ++) {
		f[0][i] = 0;
	}
	for(int i = 1;i <= w;i ++) {
		for(int j = 1;j <= b; j ++) {
			f[i][j] = 1.0 * i / (i + j);
			if(j >= 3) {
				f[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * f[i][j - 3];
			}
			if(i >= 1 && j >= 2) {
				f[i][j] += 1.0 * j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * f[i - 1][j - 2];
			}
		}
	}
	printf("%.10lf\n",f[w][b]);
	return 0;
}

这篇关于CF148D 概率dp的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！