题意：袋子里有w只白鼠和b只黑鼠。龙和公主轮流从袋子里抓老鼠。谁先抓到白色老师谁就赢。公主每次抓一只老鼠，龙每次抓完一只老鼠之后会有一只老鼠跑出来。每次抓老鼠和跑出来的老鼠都是随机的。如果两个人都没有抓到白色老鼠则龙赢。公主先抓。问公主赢的概率。

解法：就是最普通的概率DP，加了些限制条件。设p[i][j]表示袋子里有i只白鼠，j只黑鼠时，公主先抓公主赢的概率。

　　　边界条件p[0][0] = 0，p[i][0] = 1，p[0][i] = 0，p[i][1] = i / (i+1)。

　　　状态转移方程p[i][j] = i/(i+1) + j/(i+j) * (j-1)/(i+j-1) * ((j-2)/(i+j-2) * p[i][j-3] + i/(i+j-2) * p[i-1][j-2])。

tag:math, 概率dp, 水题

1 /* 2  * Author:  Plumrain 3  * Created Time:  2013-11-11 15:38 4  * File Name: DP-CF-148D.cpp 5  */ 6 #include 
      
        7 #include 
       
         8 #include 
        
          9 10 using namespace std;11 12 #define CLR(x) memset(x, 0, sizeof(x))13 14 double p[1005][1005];15 16 void DP()17 {18     CLR (p);19     for (int i = 0; i <= 1001; ++ i){20         p[i][0] = 1.0;21         p[0][i] = 0.0;22         p[i][1] = (double)i / (i + 1);23     }24     for (int i = 1; i <= 1001; ++ i)25         for (int j = 2; j <= 1001; ++ j){26             p[i][j] = (double)i / (i + j);27             double tmp = (double)j * (j-1) / (i + j) / (i + j - 1);28             if (j > 2)29                 p[i][j] += tmp * (double)(j-2)/(i+j-2) * p[i][j-3];30             p[i][j] += tmp * (double)i/(i+j-2) * p[i-1][j-2];31         }32 }33 34 int main()35 {36     DP();37     int w, b;38     while (scanf ("%d%d", &w, &b) != EOF)39         printf ("%.10f\n", p[w][b]);40     return 0;41 }