转载

Codeforces Round #105 D. Bag of mice 概率dp

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

题目意思是龙和公主轮流从袋子里抽老鼠，袋子里有白老师 W 只，黑老师 D 只，公主先抽，第一个抽出白老鼠的胜利，龙每次抽的时候会随机跑出一只老鼠。给出W和D要你求出公主胜利的概率。

对于dp[w][d]表示有w只白老鼠d只黑老鼠的情况下公主胜利的概率，如果公主第一次就抽出白鼠，概率是 w/(w+d) ，而如果公主没有抽到白鼠，要让公主胜利，龙也不能抽到白鼠，则是 rec = d/(w+d) * (d-1)/(w+d-1) 。这是跑出来的老鼠可能是白的也可能是黑的。如果是白鼠，则剩下w-1只白鼠d-2只黑鼠，然后再公主先手，概率是rec * w/(w+d-2) * dp[w-1][d-2]。如果是黑鼠，则剩下w只白鼠d-3只黑鼠，同样公主先手，概率是rec * (d-2)/(w+d-2) * dp[w][d-3];

最终得dp转移方程:

dp[i][j] = i / (i+j) + rec * (i / (i+j-2) * dp[i-1][j-2] + (j-2) / (i + j - 2) * dp[i][j-3]);

rec = j / (i + j) * (j - 1) / (i + j - 1);

/***********************************************  ** problem ID : cf_#105D.cpp  ** create time : Wed Jul 22 20:22:24 2015  ** auther name : xuelanghu  ** auther blog : blog.csdn.net/xuelanghu407  **********************************************/ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n, m; double dp[1010][1010]; int main () {  cin >> n >> m;  for (int i=0; i<=n; i++) {   dp[i][0] = 1.0;  }  for (int i=0; i<=m; i++) {   dp[0][i] = 0.0;  }  for (int i=1; i<=n; i++) {   dp[i][1] = (double)i / (i+1);   for (int j=2; j<=m; j++) {    dp[i][j] = (double)i / (i+j);    double tmp = (double)j* (double)(j-1)  / (i+j) / (i+j-1);    if (j>2) dp[i][j] += tmp * (double)(j-2) / (i+j-2) * dp[i][j-3];      dp[i][j] += tmp * (double)i / (i+j-2) * dp[i-1][j-2];   }  }  printf("%.10lf/n", dp[n][m]);  return 0; }