POJ 1191 棋盤分割：五維 DP 求最小均方差

問題轉化

8×8 棋盤，每格有分值。沿直線切割 n-1 次得到 n 個矩形（1≤n<15）。每矩形分值為格值之和。求 n 個矩形分值的最小均方差。均方差比較等價於方差比較，再等價於平方和比較。

狀態定義

dp[x1][y1][x2][y2][i] 表示矩形 (x1,y1)-(x2,y2) 分割 i 次（得 i+1 塊）的最小平方和。

狀態轉移

水平切割：枚舉切割行 j，
dp[x1][y1][x2][y2][i] = min( dp[x1][y1][j][y2][i-1] + sqr(j+1,y1,x2,y2), dp[j+1][y1][x2][y2][i-1] + sqr(x1,y1,j,y2) )

垂直切割：枚舉切割列 j，同理。取兩方向最小值。

預處理

前綴和 nSum 計算任意矩形分值和，nSquare = nSum^2。dp[][][][][0] = nSquare。

代碼框架

const int W = 8, MAXN = 16, INF = 0x3f3f3f3f;
int a[W+1][W+1], nSum[W+1][W+1][W+1][W+1], nSq[...], dp[...][MAXN];
void Init() { ... 計算 nSum, nSq, dp[*][0] ... }
void Dp(int n) {
    for (int i=1; i<=n-1; i++)
        for (int x1=W; x1>=1; x1--)
            for (int y1=1; y1<=W; y1++)
                for (int x2=x1; x2<=W; x2++)
                    for (int y2=y1; y2<=W; y2++) {
                        dp[x1][y1][x2][y2][i] = INF;
                        for (int j=x1; j