现在的位置: 首页 > 综合 > 正文

148D Bag of mice – 简单概率dp

2013年10月28日 ⁄ 综合 ⁄ 共 1089字 ⁄ 字号 评论关闭
/*
	http://codeforces.com/contest/148/problem/D Bag of mice
	题意:两个人抓老鼠,老鼠只有黑的或白色的。
	骑士抓老鼠的时候会吓跑一只老鼠,公主抓老鼠的时候不会吓跑老鼠
	谁先抓到白老鼠谁胜。
	求公主胜的概率,如果没有白老鼠可抓,则定义为公主输
	思路:定义两个数组
	dp[w][b][0]表示在w白老鼠b黑老鼠情况中公主胜的概率,
	dp[w][b][1]表示在w白老鼠b黑老鼠情况中骑士胜的概率。
	概率dp
*/

#include <stdio.h>
#include <iostream>
using namespace std;

template <typename _T>
_T gcd(_T bigger, _T smaller){
    if(smaller == 0) return bigger;
    return gcd(smaller, bigger % smaller);
}
template < typename _T>
_T Max(_T a,_T b){
    return (a>b)?(a):(b);
}
template < typename _T>
_T Max(_T a,_T b,_T c){
    return (a>Max(a,b))?(a):(Max(a,b));
}
template < typename _T>
_T Min(_T a,_T b){
    return (a<b)?(a):(b);
}

double p[1002][1002][2];
int main(){
	//freopen("in.txt","r",stdin);
	int w , b ;
	while(cin >> w >> b){
		memset(p,0,sizeof(p));
		for(int i = 1 ;  i <= w ; i++){
			p[i][0][0] = 1; // 公主先手胜的概率
			p[i][0][1] = 1; // 怪物先手胜的概率
			p[i][1][0] = 1.0/(i+1);
			p[i][1][1] = 1.0/(1+i);
		}
		p[0][0][0] = 0; p[0][0][1] = 1; p[0][1][0] = 0; p[0][1][1] = 1;
		for (int i = 1 ; i <= w ; i++){
			for (int j = 1 ; j <= b ; j++){
				p[i][j][0] = (i*1.0)/(i+j) + (j*1.0)/(i+j)*(1 - p[i][j-1][1]);
				p[i][j][1] = (i*1.0)/(i+j) + (j*1.0)/(i+j)*((1-p[i][j-2][0])*((j-1)*1.0)/(i+j-1) + (1-p[i-1][j-1][0])*(i*1.0/(i+j-1)) );
			}
		}
		printf("%.10f\n",p[w][b][0]);
	}

	return 0;
}

抱歉!评论已关闭.