POJ 1191 棋盤分割：四維區間 DP 最小化均方差

POJ 1191 棋盤分割：四維區間 DP 最小化均方差

將 8×8 棋盤切成 n (1 < n < 15) 個矩形，每次切割沿格線將一塊矩形分為兩塊矩形。每格有分值，矩形總分為內部格值之和。求最小化 n 塊矩形總分的均方差。

數學轉化

均方差 σ² = (1/n) Σ(xᵢ - μ)² = (1/n) Σxᵢ² - μ²，其中 μ = 總分 / n 為常數。
⇒ 最小化均方差 ⇔ 最小化 Σxᵢ²（各矩形分值平方和）。

狀態定義

dp[k][x1][y1][x2][y2]：將子矩形 (x1,y1)-(x2,y2) 切成 k+1 塊（即切 k 刀）的最小平方和。
座標 1-based，1 ≤ x1 ≤ x2 ≤ 8, 1 ≤ y1 ≤ y2 ≤ 8，0 ≤ k < n。

轉移方程

對矩形 R = (x1,y1,x2,y2)，嘗試所有合法切法：

• 垂直切：x = x1 … x2-1，分為 R₁=(x1,y1,x,y2)、R₂=(x+1,y1,x2,y2)。
  分配 i 刀給 R₁，k-1-i 刀給 R₂（共 k-1 刀，因本次切割佔 1 刀）。
  dp[k][R] = min(dp[i][R₁] + dp[k-1-i][R₂])。
• 水平切：同理枚舉 y 切分上下。

邊界：dp[0][R] = (sum(R))²。

預處理：二維前綴和 O(1) 取矩形和

int sum[9][9];  // sum[i][j] = (1,1) 到 (i,j) 矩形和
int rectSum(int x1, int y1, int x2, int y2) {
    return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
}

完整 AC 代碼（核心邏輯）

const int INF = 0x3f3f3f3f;
int dp[15][9][9][9][9];  // [k][x1][y1][x2][y2]
int sq[9][9][9][9];      // 預計算各矩形平方和

int main() {
    int n;
    while (cin >> n) {
        // 讀入棋盤、建立前綴和、預計算 sq
        memset(dp, 0x3f, sizeof(dp));
        for (int x1=1; x1<=8; ++x1)
            for (int y1=1; y1<=8; ++y1)
                for (int x2=x1; x2<=8; ++x2)
                    for (int y2=y1; y2<=8; ++y2) {
                        int s = rectSum(x1,y1,x2,y2);
                        sq[x1][y1][x2][y2] = s * s;
                        dp[0][x1][y1][x2][y2] = sq[x1][y1][x2][y2];
                    }

        for (int k = 1; k < n; ++k)          // 切 k 刀 → k+1 塊
            for (int x1=1; x1<=8; ++x1)
                for (int y1=1; y1<=8; ++y1)
                    for (int x2=x1; x2<=8; ++x2)
                        for (int y2=y1; y2<=8; ++y2) {
                            // 垂直切
                            for (int x = x1; x < x2; ++x)
                                for (int i = 0; i < k; ++i)
                                    dp[k][x1][y1][x2][y2] = min(
                                        dp[k][x1][y1][x2][y2],
                                        dp[i][x1][y1][x][y2] + dp[k-1-i][x+1][y1][x2][y2]
                                    );
                            // 水平切
                            for (int y = y1; y < y2; ++y)
                                for (int i = 0; i < k; ++i)
                                    dp[k][x1][y1][x2][y2] = min(
                                        dp[k][x1][y1][x2][y2],
                                        dp[i][x1][y1][x2][y] + dp[k-1-i][x1][y+1][x2][y2]
                                    );
                        }

        double total = rectSum(1,1,8,8);
        double mu = total / n;
        double min_sq_sum = dp[n-1][1][1][8][8];
        double variance = min_sq_sum / n - mu * mu;
        printf("%.3f\n", sqrt(max(0.0, variance)));  // 避免負零
    }
    return 0;
}

複雜度分析

• 狀態數：n × 8⁴ ≈ 14 × 4096 ≈ 5.7×10⁴。
• 轉移：每狀態枚舉切線（≤7）× 刀數分配（≤13）× 2 方向 ≈ 200。
  總操作 ~10⁷，1s 內輕鬆通過。
• 空間：15×9⁴ ≈ 10⁵ int，< 1 MB。

關鍵優化技巧

1. 預計算平方和：避免重複計算 rectSum()²。
2. 刀數分配優化：實際可只枚舉 i=0..k-1，對稱性可減半（但 n 很小，無需）。
3. 初始化 INF：memset(dp, 0x3f, ...) 快速置大值。

總結

POJ 1191 是二維區間 DP的經典：將均方差最小化轉化為平方和最小化，狀態包含「矩形座標 + 切割次數」，轉移枚舉切線與刀數分配。預處理前綴和與平方和、合理循環順序，即可高效求解。同類思想廣泛應用於圖像分割、矩陣分塊等問題。