1 /*
2 题意：求每行每列都至少有一颗石子的天数期望值
3 概率DP：先求概率，再算期望，dp[i][j][k]表示一共放了i颗石子，j行k列至少有一颗的概率
4 由四种状态转移来，行+1， 列+1，行列+1，行列不加。另外，这样写法相当于剪枝，减少时间消耗
5 */
6 /************************************************
7 * Author :Running_Time
8 * Created Time :2015-8-16 19:58:14
9 * File Name :D_2.cpp
10 ************************************************/
11
12 #include <cstdio>
13 #include <algorithm>
14 #include <iostream>
15 #include <sstream>
16 #include <cstring>
17 #include <cmath>
18 #include <string>
19 #include <vector>
20 #include <queue>
21 #include <deque>
22 #include <stack>
23 #include <list>
24 #include <map>
25 #include <set>
26 #include <bitset>
27 #include <cstdlib>
28 #include <ctime>
29 using namespace std;
30
31 #define lson l, mid, rt << 1
32 #define rson mid + 1, r, rt << 1 | 1
33 typedef long long ll;
34 const int MAXN = 55;
35 const int INF = 0x3f3f3f3f;
36 const int MOD = 1e9 + 7;
37 double dp[MAXN*MAXN][MAXN][MAXN];
38
39 int main(void) { //ZOJ 3822 Domination
40 int T; scanf ("%d", &T);
41 while (T--) {
42 int n, m; scanf ("%d%d", &n, &m);
43 memset (dp, 0, sizeof (dp));
44 dp[1][1][1] = 1.0; int tot = n * m;
45 for (int i=1; i<=tot; ++i) {
46 for (int j=1; j<=n; ++j) {
47 for (int k=1; k<=m; ++k) {
48 if (dp[i][j][k] > 0) {
49 dp[i+1][j+1][k+1] += dp[i][j][k] / (tot - i) * (n - j) * (m - k);
50 dp[i+1][j+1][k] += dp[i][j][k] / (tot - i) * (n - j) * k;
51 dp[i+1][j][k+1] += dp[i][j][k] / (tot - i) * (m - k) * j;
52 if (j < n || k < m) {
53 dp[i+1][j][k] += dp[i][j][k] / (tot - i) * (j * k - i);
54 }
55 }
56 }
57 }
58 }
59
60 double ans = 0.0;
61 for (int i=1; i<=tot; ++i) ans += dp[i][n][m] * i;
62 printf ("%.10f
", ans);
63 }
64
65 return 0;
66 }
概率DP ZOJ 3822 Domination
编译人生，运行世界！