【CF】148D Bag of mice

http://codeforces.com/problemset/problem/148/D

题意：w个白b个黑，公主和龙轮流取，公主先取，等概率取到一个。当龙取完后，会等概率跳出一只。（0<=w, b<=1000）

#include <bits/stdc++.h>

using namespace std;

int n, m;

const int N=1005;

double d[N][N][2];

int main() {

	scanf("%d%d", &n, &m);

	d[0][0][0]=0;

	d[0][0][1]=1;

	for(int i=1; i<=n; ++i) d[i][0][0]=d[i][0][1]=1;

	for(int j=1; j<=m; ++j) d[0][j][1]=1;

	for(int i=1; i<=n; ++i)

		for(int j=1; j<=m; ++j) {

			d[i][j][0]=(double)i/(i+j)+(1-d[i][j-1][1])*j/(i+j);

			if(i==1 && j==1) d[i][j][1]=1;

			else if(i>1 && j==1) d[i][j][1]=(double)i/(i+j);

			else d[i][j][1]=(double)i/(i+j)+(((1.0-d[i-1][j-1][0])*i+(1.0-d[i][j-2][0])*(j-1))/(i+j-1))*j/(i+j);

		}

	//for(int k=0; k<2; ++k) for(int i=0; i<=n; ++i) for(int j=0; j<=m; ++j) printf("d[%d][%d][%d]:%.3f\n", i, j, k, d[i][j][k]);

	printf("%.15f\n", d[n][m][0]);

	return 0;

}

写完这题后发现一个sb问题QAQ i/(i+j) 默认调用整数的除法QAQ 没发现前我一直在纠结，我的思路完全没错啊QAQ可是为嘛有问题。最后是在写了后边的题发现了这个问题然后就QAQ解决了...

设$d[i][j][0]$表示公主先手有$i$个白$j$个黑能赢的概率，$d[i][j][1]$表示龙先手有$i$个白$j$个黑能赢的概率

显然

王妃抓时：
1、抓到白，P=i/(i+j)
2、抓到黑，P=j/(i+j)
d[i][j][0]=i/(i+j)+(1-d[i][j-1][1])*j/(i+j)

龙抓时：
抓到黑：P=j/(i+j)
跳出了白：P=i/(i+j-1)
跳出了黑：P=(j-1)/(i+j-1)
抓到白：P=i/(i+j)

d[i][j][1]=i/(i+j)+(((1-d[i-1][j-1][0])*i+(1-d[i][j-2][0])*(j-1))/(i+j-1))*j/(i+j)

自行理解= =

巴特西

【CF】148D Bag of mice

最新文章

热门文章