ZOJ 3822 Domination：概率 DP 期望覆蓋步數

ZOJ 3822 Domination：概率 DP 期望覆蓋步數

N×M 棋盤，每步均勻隨機選一格標記。求期望步數使所有行列均至少有一格被標記（即覆蓋所有行和列）。步數上限隱含有限。

方法一：正向 DP 求期望

狀態 dp[i][j][k]：已覆蓋 i 行 j 列，走了 k 步，最終能完全覆蓋的期望剩餘步數。

轉移（從大到小枚舉 i,j,k）：

p0 = (i*j - k) / (N*M - k);      // 選已覆蓋格
p1 = (M-j)*i / (N*M - k);         // 選新列舊行
p2 = (N-i)*j / (N*M - k);         // 選新行舊列
p3 = (N-i)*(M-j) / (N*M - k);     // 選新行新列
dp[i][j][k] = dp[i][j][k+1]*p0 + dp[i][j+1][k+1]*p1 + dp[i+1][j][k+1]*p2 + dp[i+1][j+1][k+1]*p3 + 1;

答案 dp[0][0][0]。

方法二：反向 DP 求概率分布再計算期望

狀態 dp[i][j][k]：走 k 步覆蓋 i 行 j 列的概率。

dp[1][1][1] = 1;
for i=1..N, j=1..M:
  for k=max(i,j)..i*j:
    dp[i][j][k+1] += dp[i][j][k] * (i*j-k)/(N*M-k);
    dp[i+1][j][k+1] += dp[i][j][k] * (N-i)*j/(N*M-k);
    dp[i][j+1][k+1] += dp[i][j][k] * (M-j)*i/(N*M-k);
    dp[i+1][j+1][k+1] += dp[i][j][k] * (N-i)*(M-j)/(N*M-k);
期望 = Σ k * dp[N][M][k];

完整代碼（方法一）

#include <cstdio> #include <cstring> #include <iostream>
#define maxn 55
double dp[maxn][maxn][maxn*maxn];
int N,M,T;
int main() {
    while (~scanf("%d", &T)) while (T--) {
        scanf("%d%d", &N, &M);
        memset(dp, 0, sizeof(dp));
        for (int i = N; i >= 0; i--)
            for (int j = M; j >= 0; j--) {
                if (i==N && j==M) continue;
                for (int k = i*j; k >= max(i,j); k--) {
                    double p0 = 1.0*(i*j-k)/(N*M-k);
                    double p1 = 1.0*(M-j)*i/(N*M-k);
                    double p2 = 1.0*(N-i)*j/(N*M-k);
                    double p3 = 1.0*(N-i)*(M-j)/(N*M-k);
                    dp[i][j][k] = dp[i][j][k+1]*p0 + dp[i][j+1][k+1]*p1 + dp[i+1][j][k+1]*p2 + dp[i+1][j+1][k+1]*p3 + 1;
                }
            }
        printf("%.12lf\n", dp[0][0][0]);
    }
    return 0;
}

關鍵點

• 步數 k 範圍：max(i,j) ≤ k ≤ i*j。
• 分母 N*M-k 為剩餘未選格子數。
• 雙重循環順序：i,j 從大到小，k 從大到小，保證依賴已計算。
• 精度用 double 足夠，輸出 %.12lf。

複雜度

• 時間：O(N²M²)，N,M≤50 約 6e6 狀態，可行。
• 空間：O(N²M²)，約 55³ ≈ 166k double ≈ 1.3MB。

此題是概率 DP 計算期望的經典模型，展示了「正向期望 DP」與「反向概率 DP」兩種等價視角，是狀態壓縮概率 DP 的優秀練習。