CF148D Bag of mice

思路:概率入门.对于这种概率dp题,一般是概率体现在转移上. 状态当然是你有w个白老鼠,b个黑老鼠时,A赢的概率. 然后显然只有两个人同时鬼抽两个黑老鼠的时候才能继续下一步的概率,然后计算出中间赢的概率即可.

#include
using namespace std;
const int maxn = 1000+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
double dp[maxn][maxn];
double dfs(int w,int b){
	if(w==0) return 0.0;
	if(b==0) return 1.0;
	if(dp[w][b]>0) return dp[w][b];
	double &ans = dp[w][b];
	int cur = w+b;
	ans+=1.0*w / cur;
	if(b==2) {
		//A draw a black && B draw a black
		ans += (1.0*b/cur) * (1.0*(b-1)/(cur-1)) * dfs(w,b-2); 
	}
	else if(b>=3){
		// A draw a black && B draw a black and 随机扔一个老鼠
		ans+= (1.0*b/cur) * (1.0*(b-1)/(cur-1)) * (  1.0*w /(cur-2)*dfs(w-1,b-2) + 1.0*(b-2)/(cur-2)*dfs(w,b-3));
	}
	return ans; 
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int w,b;
	cin>>w>>b;
	printf("%.9lf",dfs(w,b));
}