程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CF D. Bag of mice(概率dp)

CF D. Bag of mice(概率dp)

編輯：C++入門知識

CF D. Bag of mice(概率dp)

這裡有w只白鼠和b只黑鼠，龍和王妃輪流從袋子裡抓鼠，每次抓一只，抓到第一只白鼠的人獲勝。當龍抓一只鼠時，袋子裡會跑掉一只鼠，跑掉的鼠是等概率的。問王妃獲勝的概率。

設有i只白鼠j只黑鼠的狀態下王妃獲勝的概率是dp[i][j]，這種狀態可由一下三種狀態得到：

王妃第一次就取得一只白鼠獲勝，概率為i/(i+j)；

王妃沒有取到白鼠，取黑鼠的概率是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];

綜上，dp[i][j] = i/(i+j) + 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 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL __int64
#define LL long long
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;
double dp[1010][1010];

int main()
{
	int w,b;
	while(~scanf(%d %d,&w,&b))
	{
		for(int i = 1; i <= w; i++)
			dp[i][0] = 1;
		for(int i = 0; i <= b; i++)
			dp[0][i] = 0;
		for(int i = 1; i <= w; i++)
		{
			for(int j = 1; j <= b; j++)
			{
				dp[i][j] = i*1.0/(i+j);
				if(j >= 2)
					dp[i][j] += j*1.0/(i+j) * (j-1)*1.0/(i+j-1) * (i*1.0)/(i+j-2) * dp[i-1][j-2];
				if(j >= 3)
					dp[i][j] += j*1.0/(i+j) * (j-1)*1.0/(i+j-1) * (j-2)*1.0/(i+j-2) * dp[i][j-3];
			}
		}
		printf(%.9lf
,dp[w][b]);
	}
	return 0;
}