【題意】：有一個裝著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