Codeforces Round #105 (Div. 2) D 概率DP

Codeforces Round #105 (Div. 2) D 概率DP

題目

呃 琢磨了半天還是琢磨出來了，題意有些模糊哈，有w個白色物品，b個黑色物品，A,B輪著抽，A先開始，誰先抽到白色誰贏，若最終都沒有抽到白色 則算B贏，抽出來的物品不會放回去，B抽完以後 物品還會有一個額外產生丟失，問A贏的概率為多少

依舊是以目標狀態為邊界，當前狀態到目標狀態所需要的概率為 方程

dp[i][j] 代表當前輪到A抽的時候，還有i個白色的j個黑色的A贏的概率為多少

則當前轉移可能有四種

1:A抽到了白色的，那麼直接贏了，接下來不需要繼續，所以沒有與其它狀態方程有聯系

2：A抽到了黑色的,下一次B抽到了白色的 那麼A輸了，輸了就結束了 對下面我們要求的答案無影響，所以不管這一個

3：A抽到了黑色，下一次B又抽到了黑色，且丟失的為白色的，也就是dp[i - 1][j - 2]，因為這個都沒有產生絕對贏輸的狀態，所以會對下面的方程轉移遞推有幫助，所以需要聯系上

4：A抽到了黑色，下一次B抽到了黑色，且丟失的為黑色，也就是dp[i][j - 3]，這個也沒有產生絕對的輸贏，所以還是需要聯系上

那麼邊界dp[0][0] = 0,因為輪到A的時候沒有可以抽的了，表示都抽光了，這時候按照題目條件算B贏的

還有dp[i][0]輪到A抽的時候 黑色的已經沒有了，那麼A只能抽白色的 所以肯定贏咯

還有dp[0][j]輪到A的時候白色的沒有了，所以必輸

double dp[1000 + 55][1000 + 55];

int w,b;

void init() {
	memset(dp,0.00,sizeof(dp));
}

bool input() {
	while(cin>>w>>b) {

		return false;
	}
	return true;
}

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

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}