Codeforces 148D Bag of mice(概率dp)

黑箱子里有w只白老鼠和b只黑老鼠，dragon和Princess轮流从箱子中拿出一只老鼠，先取到白老鼠的人赢，但是dragon每次拿的时候都会多跑出一只老鼠。

思路分析：

dp[i][j] 表示箱子里有i只白老鼠和j只黑老鼠的时候 Princess 先取赢的概率。

那么转移方程就有4个。

分别是 ：

直接取到白老鼠

取到黑老鼠，dragon也拿到了黑老鼠，跑了一只黑老鼠。

取到黑老鼠，dragon也拿到了黑老鼠，跑了一支白老鼠。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

double dp[1005][1005];

int main(){
	int w,b;
	cin>>w>>b;

	for(int i=1;i<=w;i++){
		dp[i][0]=1.0;
	}
	for(int i=1;i<=b;i++){
		dp[0][i]=0.0;
	}
	
	for(int i=1;i<=w;i++){
		for(int j=1;j<=b;j++){
			dp[i][j]=0.0;
			dp[i][j]+=1.0*i/(i+j);
			if(j>=3)
				dp[i][j]+=1.0*j/(i+j)*1.0*(j-1)/(i+j-1)*1.0*(j-2)/(i+j-2)*dp[i][j-3];
			if(j>=2)
				dp[i][j]+=1.0*j/(i+j)*1.0*(j-1)/(i+j-1)*1.0*(i)/(i+j-2)*dp[i-1][j-2];
		}
	}
	printf("%.9lf\n",dp[w][b]);
	return 0;
}

Codeforces 148D Bag of mice(概率dp)

原文：http://blog.csdn.net/u010709592/article/details/42873527