形式化题目

给定一个 $8 \times 8$ 的矩阵 $a$，把棋盘切成 $n$ 块矩形。切法只有一种形式：每一刀沿着格子边把当前这块矩形切成两块，其中一块就此定稿、不再参与后续切割，另一块继续切；共切 $n-1$ 刀。

设第 $i$ 块矩形的分值总和为 $x_i$，$\bar{x} = \frac{1}{n}\sum_{i=1}^{n}x_i$，求

的值，四舍五入到小数点后三位。

注意“割下一块、剩下的继续切”与“每次把矩形分成两块、两块都继续切”不是同一个问题：第一种读法每刀只有一侧存活，可行切法更少，最优值只会更大。两种模型在同一组棋盘上给出的答案差别很大，后面会用一个反例具体说明。

以样例（$n = 3$，棋盘总分 $T = 66$，平均值 $\bar{x} = 22$）为例，最优切法先割下第 5~7 行（记为 A，$x_A = 24$），再把剩下的 $5 \times 8$ 矩形竖着切成左右两半（记为 B、C，$x_B = 20$、$x_C = 22$）。下表把 64 个格子按块标出：

三块分值 $20 + 22 + 24 = 66$ 与总分吻合；$\sqrt{\frac{20^2+22^2+24^2}{3} - 22^2} = \sqrt{\frac{1460}{3} - 484} \approx 1.633$，正是样例输出。读表时注意两件事：每块都是矩形而不是任意形状；三块分值 $20,22,24$ 已经非常接近平均值 $22$，这正是最小化均方差要达到的效果。

正解

思路

朴素做法与瓶颈

最直接的做法是搜索所有切割顺序：每一步在当前矩形上选一条切线和方向，割下的块记入答案，剩下的矩形继续切，直到凑满 $n$ 块。第一刀有 $2\times(7+7)=28$ 种选择，之后每一刀仍有十几到二十几种，搜索树在 $n=14$ 时完全不可行。

真正的瓶颈不在枚举量，而在没有合并重复子问题。观察搜索过程：每一步只改变两件事——当前的剩余矩形、还要切出几块；被割下的块此后只贡献一个固定的 $S^2$，不再影响后续。也就是说，同一组“剩余矩形 + 剩余块数”会在大量不同的搜索路径上被反复求解。把它记下来就是 DP。

题面里“剩下的部分也是矩形”这句话正是这个状态成立的原因：剩余部分总能被四个整数 $r_1,c_1,r_2,c_2$ 描述。

第一步：化简目标函数

棋盘总分 $T = \sum x_i$ 和块数 $n$ 都是常数，$\bar{x} = T/n$ 也固定，所以最小化 $\sigma$ 等价于最小化整数 $\sum x_i^2$。这样 DP 全程只做整数加法与比较，浮点只在最后开一次根。

第二步：状态与转移

设 $f(r_1,c_1,r_2,c_2,k)$ 表示：把矩形 $[r_1,r_2]\times[c_1,c_2]$ 切成 $k$ 块时，$\sum x_i^2$ 的最小值。用 $S(\cdot)$ 表示矩形分值之和（二维前缀和 $O(1)$ 求出），则

其中 $(A,B)$ 遍历所有“割下 $A$、剩下 $B$”的一刀。这一刀有四类：割走上半、割走下半、割走左半、割走右半；代码把它们写成四个生成器，用 itertools.chain 接起来，于是转移体里只剩一种写法。

之所以只对 $B$ 继续递归，就是前面强调的“每刀只有一侧存活”。若把转移写成两侧都要继续切的通用形式

可行切法会变多、答案会偏小：真实数据 chess2 用这个形式会得到 $0.000$，而正确答案是 $2.449$；chess5 会得到 $15.937$，正确答案是 $75.263$。

用样例看状态表

下表的每一行是一个子问题，列出矩形和 $S$、最优值 $f$ 以及首刀决策，数值来自样例的完整 DP。第一行 $f = 66^2 = 4356$ 就是 $k=1$ 的边界条件：整块不切时分值平方和就是它自己的平方：

校验最后一步：$f(0,0,7,7,3) = 24^2 + f(0,0,4,7,2) = 576 + 884 = 1460$。注意 $f$ 只随 $k$ 增大而减小（$4356 \to 2180 \to 1460$），因为切得越细，各块越接近平均值。

为什么不用递推而用记忆化

按 $k$ 从小到大、子矩形从小到大递推当然也可以，但“子矩形的包含关系”和“$k$ 的递减关系”要手工排序，还要为每个 $k$ 开一张 $1296$ 大小的表。本题的状态空间只有约 $1.8\times10^{4}$，直接用 functools.cache 记忆化，让递归自己决定访问顺序，代码短得多，代价只是常数级的时间开销。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 棋盘分割：记忆化搜索最小化各块分值平方和，最后换算成均方差
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long ll;

const int SIZE = 8;    // 棋盘边长固定为 8
const int MAXK = 20;   // 切块数上界
const ll INF = 1000000000000000000LL; // 一块也切不动时的不可行代价

int cells[SIZE][SIZE];
ll pre[SIZE + 1][SIZE + 1]; // 二维前缀和
ll memo[SIZE][SIZE][SIZE][SIZE][MAXK + 1]; // best(r1,c1,r2,c2,k) 的缓存，-1 表示未算

// 闭区间矩形 [r1,r2] x [c1,c2] 的分值之和
ll box(int r1, int c1, int r2, int c2) {
    return pre[r2 + 1][c2 + 1] - pre[r1][c2 + 1] - pre[r2 + 1][c1] + pre[r1][c1];
}

// 把矩形切成 k 块时各块分值平方和的最小值
ll best(int r1, int c1, int r2, int c2, int k) {
    if (k == 1) {
        ll s = box(r1, c1, r2, c2);
        return s * s;
    }
    ll& res = memo[r1][c1][r2][c2][k];
    if (res >= 0) {
        return res;
    }
    ll ans = INF;
    // 横着切：上面一块定稿，下面一块还要再切 k-1 刀
    for (int i = r1; i < r2; i++) {
        ll s1 = box(r1, c1, i, c2);
        ll v = s1 * s1 + best(i + 1, c1, r2, c2, k - 1);
        if (v < ans) {
            ans = v;
        }
        ll s2 = box(i + 1, c1, r2, c2);
        v = s2 * s2 + best(r1, c1, i, c2, k - 1);
        if (v < ans) {
            ans = v;
        }
    }
    // 竖着切：左一块定稿，右一块还要再切 k-1 刀
    for (int j = c1; j < c2; j++) {
        ll s1 = box(r1, c1, r2, j);
        ll v = s1 * s1 + best(r1, j + 1, r2, c2, k - 1);
        if (v < ans) {
            ans = v;
        }
        ll s2 = box(r1, j + 1, r2, c2);
        v = s2 * s2 + best(r1, c1, r2, j, k - 1);
        if (v < ans) {
            ans = v;
        }
    }
    res = ans;
    return ans;
}

int main() {
    for (int r = 0; r < SIZE; r++) {
        for (int c = 0; c < SIZE; c++) {
            for (int a = 0; a < SIZE; a++) {
                for (int b = 0; b < SIZE; b++) {
                    for (int k = 0; k <= MAXK; k++) {
                        memo[r][c][a][b][k] = -1;
                    }
                }
            }
        }
    }
    int n;
    if (scanf("%d", &n) != 1) {
        return 0;
    }
    for (int r = 0; r < SIZE; r++) {
        for (int c = 0; c < SIZE; c++) {
            scanf("%d", &cells[r][c]);
            pre[r + 1][c + 1] = pre[r][c + 1] + pre[r + 1][c] - pre[r][c] + cells[r][c];
        }
    }
    ll total = pre[SIZE][SIZE];
    ll s2 = best(0, 0, SIZE - 1, SIZE - 1, n); // Σx² 的最小值
    double ans = sqrt((double)s2 / n - ((double)total / n) * ((double)total / n));
    printf("%.3f\n", ans);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 10:20
# update_at: 2026-10-02 10:20

import sys
from functools import cache
from itertools import chain
from math import sqrt

SIZE = 8      # 棋盘边长固定为 8
INF = 10**18  # 矩形小到一刀也下不去时的不可行代价

PREFIX: list[list[int]] = []  # (SIZE+1) x (SIZE+1) 的二维前缀和，由 solve 填入


def prefix_of(cells: list[int]) -> list[list[int]]:
    """把行优先读入的 64 个格子分值变成二维前缀和，使任意子矩形和 O(1) 可求。"""
    P = [[0] * (SIZE + 1) for _ in range(SIZE + 1)]
    for r in range(SIZE):
        for c in range(SIZE):
            P[r + 1][c + 1] = P[r][c + 1] + P[r + 1][c] - P[r][c] + cells[SIZE * r + c]
    return P


def box(r1: int, c1: int, r2: int, c2: int) -> int:
    """闭区间矩形 [r1,r2] x [c1,c2] 的分值之和。"""
    return PREFIX[r2 + 1][c2 + 1] - PREFIX[r1][c2 + 1] - PREFIX[r2 + 1][c1] + PREFIX[r1][c1]


def cuts(r1: int, c1: int, r2: int, c2: int):
    """枚举“割下一块矩形、剩下部分仍是矩形”的所有一刀，产出 (割下的块, 剩下的块)。"""
    return chain(
        (((r1, c1, i, c2), (i + 1, c1, r2, c2)) for i in range(r1, r2)),  # 割走上半
        (((i + 1, c1, r2, c2), (r1, c1, i, c2)) for i in range(r1, r2)),  # 割走下半
        (((r1, c1, r2, j), (r1, j + 1, r2, c2)) for j in range(c1, c2)),  # 割走左半
        (((r1, j + 1, r2, c2), (r1, c1, r2, j)) for j in range(c1, c2)),  # 割走右半
    )


@cache
def best(r1: int, c1: int, r2: int, c2: int, k: int) -> int:
    """把矩形切成 k 块时各块分值平方和的最小值（均方差只与它相差一个常数）。"""
    if k == 1:
        return box(r1, c1, r2, c2) ** 2
    return min(
        # 割下的那块就此定稿，剩下那块还要再切 k-1 刀
        (box(*peeled) ** 2 + best(*kept, k - 1) for peeled, kept in cuts(r1, c1, r2, c2)),
        default=INF,  # 单格矩形切不出两块
    )


def solve() -> None:
    global PREFIX
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, *cells = data
    PREFIX = prefix_of(cells)
    total = PREFIX[SIZE][SIZE]
    s2 = best(0, 0, SIZE - 1, SIZE - 1, n)  # Σx² 的最小值
    # 均方差 = sqrt(Σx²/n - (Σx/n)²)：n 与总分 Σx 固定，所以只需最小化 Σx²
    print(f"{sqrt(s2 / n - (total / n) ** 2):.3f}")


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：状态数为子矩形个数 $\binom{9}{2}^{2} = 1296$ 乘以剩余块数 $k \leqslant 14$，约 $1.8\times10^{4}$；每个状态枚举一刀，水平线 $r_2-r_1$ 条、竖直线 $c_2-c_1$ 条、各带两个方向，候选数不超过 $28$。转移总量的上界约 $1.8\times10^{4} \times 28 \approx 5\times10^{5}$，实测最慢一组（$n = 14$）只访问了 9296 个状态、0.044 s。
• 空间复杂度：记忆化缓存 $O\bigl(36^2 \cdot n\bigr) = O(10^4)$ 个整数，加上 $9\times 9$ 的前缀和；实测峰值内存 16.6 MB。

总结

本题有两步是绕不开的。第一步是把均方差化简掉：总分和块数固定，均方差只通过 $\sum x_i^2$ 依赖切法，于是连续优化变成整数最优化。第二步是选对状态：题面“割下一块、剩下的继续切”保证剩余待切部分永远是矩形，用「剩余矩形 + 还要切几块」两个信息就足以描述子问题，被割下的块只留下 $S^2$ 这一个常数贡献。剩下的就是枚举一刀并记忆化。

最容易出错的是把题意读成“每次分成两块、两块都继续切”，那会让答案系统性偏小；真实数据里 chess2 与 chess5 都能立刻暴露这个错误。

图示解析

下面用样例的决策链展示 $f(\text{整盘},3)$ 是怎样一步步拆开的。标着 $f$ 的结点是“还剩一块要切”的状态，标注矩形和 $S$ 与当前 $f$ 值；缩进在它上面的那一行是“这一刀割下的矩形”，它只贡献一个 $S^2$，不再往下分叉。

1
2
3
4
5f(整盘 8x8, 3)          S=66  f=1460
├─ 割下第 5~7 行          S=24 → 24² = 576
└─ f(第 0~4 行 5x8, 2)   S=42  f=884
   ├─ 割下左 4 列         S=20 → 20² = 400
   └─ f(右 4 列, 1)       S=22  f=484

读图时关注三点：每层的 $k$ 恰好减一；每一刀都只“割下一块、保留一块”，所以每层只有一条线继续往下画；把最底下三个数值加起来，$576 + 400 + 484 = 1460$ 正是 $f(\text{整盘},3)$，也就是样例答案里开方前的 $\sum x_i^2$。这条链就是 DP 从根状态一路递归下去时真正走的路径。

再下面这张图概括转移的一般形态：一个状态只在两种情况下终止或分叉。

flowchart TD
  S["状态：矩形 [r1,r2] x [c1,c2]，还要切 k 块"] --> C{"k == 1 ?"}
  C -- 是 --> B["整块定稿<br/>f = S(矩形)²"]
  C -- 否 --> D["枚举一刀，分成 A 与 B<br/>A 是割下的那块"]
  D --> E["A 定稿：贡献 S(A)²"]
  D --> F["B 继续切 k-1 块<br/>递归 f(B, k-1)"]
  E --> G["两者相加，对所有一刀取最小"]
  F --> G

图里两条分叉对应题面里“割下一块”和“剩下部分继续分割”这两件事；注意从 $D$ 出发只有 $B$ 一条边会回到状态结点，这正是本题与通用 guillotine 切分的分水岭。