【题意】：有一个装着w只白鼠和b只黒鼠的袋子，现在公主和龙轮流在袋子里摸出一只老鼠（不放回），谁先摸出白鼠就胜出，公主先手。由于龙摸老鼠的动作较大 ，所以龙每次摸出一只老鼠后，袋子里会随机跑走一只老鼠。如果当前没有了白鼠，一律为龙胜，问公主获胜的机率有多大。
【题解】：好明显的概率dp，比赛时居然不够胆开，晕了，水平还是不够。
今天认真想了一下，发现是很简单的概率dp，亏了。
设f[i][j] 表示当前袋子有 i 只白鼠和 j 只黑鼠，公主摸完后胜出的机率。
g[i][j] 表示当前袋子有 i 只白鼠和 j 只黒鼠，龙摸完后胜出的机率。
状态转移:
f[i][j] = i / (i + j) + j * (1 - g[i][j-1]) / (i + j);
g[i][j] = i / (i + j) + j / (i + j) * (i / (i + j - 1) * (1 - f[i-1][j-1]) + (j - 1) / (i + j - 1) * (1 - f[i][j-2]));
递推一次 O(n*n), 答案即为f[w][b].
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define MAX 1005
19 int w, b;
20 double f[MAX][MAX], g[MAX][MAX];
21 int main() {
22 while(cin >> w >> b) {
23 for(int i = 0; i <= b; i++) f[0][i] = 0.0, g[0][i] = 1.0;
24 for(int i = 1; i <= w; i++) f[i][0] = g[i][0] = 1.0;
25 for(int i = 1; i <= w; i++) {
26 for(int j = 1; j <= b; j++) {
27 double tmp = 0.0;
28 f[i][j] = 1.0 * i / (i + j) + 1.0 * j * (1 - g[i][j-1]) / (i + j);
29 if(j >= 2) tmp = 1.0 * (j - 1) / (i + j - 1) * (1 - f[i][j-2]);
30 g[i][j] = 1.0 * i / (i + j) + 1.0 * j * (i * (1 - f[i-1][j-1]) / (i + j - 1) + tmp) / (i + j);
31 }
32 }
33 printf("%.10f\n", f[w][b]);
34 }
35 return 0;
36 }
37