ZOJ 3822: Domination - 期望 DP 解棋盤覆蓋問題

問題描述

N×M 棋盤，每天隨機在空格放一子。求期望天數使得每行每列至少有一子（即棋盤被「統治」）。

狀態定義

dp[r][c][k]：左上角 r 行 c 列區域內已有 k 個子的情況下，達到目標的期望剩餘天數。利用對稱性，只關注已覆蓋的行數、列數及區域內子數。

轉移方程

總格數 tot = N*M，區域內格數 rc = r*c，已放子數 k。
下一子落在：
1. 區域內空格：概率 (rc-k)/(tot-k)，狀態 (r,c,k+1)
2. 新行舊列：(N-r)*c/(tot-k)，狀態 (r+1,c,k+1)
3. 舊行新列：r*(M-c)/(tot-k)，狀態 (r,c+1,k+1)
4. 新行新列：(N-r)*(M-c)/(tot-k)，狀態 (r+1,c+1,k+1)
dp[r][c][k] = 1 + Σ prob * dp[next]。邊界：r==N && c==M → 0；r==0 || c==0 → dp[1][1][1]+1。記憶化遞歸計算。

複雜度

狀態數 O(N²M²) ≈ 50⁴ = 6.25M，轉移 O(1)，8 秒時限內可行。