题目描述

将一个 $8 \times 8$ 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了 $(n-1)$ 次后，连同最后剩下的矩形棋盘共有 $n$ 块矩形棋盘（每次切割都只能沿着棋盘格子的边进行）。

原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。

现在需要把棋盘按上述规则分割成 $n$ 块矩形棋盘，并使各矩形棋盘总分的均方差最小。

均方差公式：

$$\sigma = \sqrt{ \frac{ \sum_{i=1}^n (x_i - \bar{x})^2 }{n} }$$

其中平均值：

$$\bar{x} = \frac{\sum_{i=1}^n x_i}{n}$$

$x_i$ 为第 $i$ 块矩形棋盘的总分。

请编程对给出的棋盘及 $n$，求出均方差的最小值。

输入格式

第 1 行为一个整数 $n$。

第 2 行至第 9 行每行为 8 个小于 100 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

输出格式

输出最小均方差值（四舍五入精确到小数点后三位）。

样例

3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3

1.633

样例解释

棋盘数据

$n = 3$，棋盘大小为 $8 \times 8$，分值矩阵见输入。

分割要求

需要将棋盘切割成 $3$ 块矩形（即切 $2$ 刀），使得这 $3$ 块的总分均方差最小。

计算过程

首先计算整个棋盘的总分 $sum$，平均值 $\bar{x} = \frac{sum}{3}$。

我们需要找到一种分割方式，使得 $3$ 块棋盘的总分 $x_1, x_2, x_3$ 满足 $\sum_{i=1}^3 (x_i - \bar{x})^2$ 最小。

由于均方差 $\sigma = \sqrt{ \frac{ \sum (x_i - \bar{x})^2 }{n} }$，最小化 $\sigma$ 等价于最小化 $\sum (x_i - \bar{x})^2$。

最优分割

通过动态规划枚举所有可能的分割方式，可以求得最小 $\sum (x_i - \bar{x})^2$，然后计算 $\sigma$。

根据输出，最小均方差为 $1.633$。

数据范围

• $1 < n < 15$（即 $n$ 的取值范围是 $2 \le n \le 14$）
• 棋盘大小固定 $8 \times 8$
• 每个格子分值 $< 100$

算法分析

这是一个二维区间 DP问题，需要将棋盘分割成 $n$ 个矩形，求最小均方差。

数学转化

设总分为 $sum$，平均值为 $\bar{x} = \frac{sum}{n}$。

均方差 $\sigma = \sqrt{ \frac{ \sum_{i=1}^n (x_i - \bar{x})^2 }{n} }$。

由于 $\bar{x}$ 是常数，最小化 $\sigma$ 等价于最小化 $\sum_{i=1}^n (x_i - \bar{x})^2 = \sum_{i=1}^n x_i^2 - 2\bar{x}\sum_{i=1}^n x_i + n\bar{x}^2 = \sum_{i=1}^n x_i^2 - \frac{sum^2}{n}$。

因为 $\sum_{i=1}^n x_i = sum$ 是定值，所以最小化 $\sum (x_i - \bar{x})^2$ 等价于最小化 $\sum_{i=1}^n x_i^2$。

因此，问题转化为：将棋盘分割成 $n$ 个矩形，使得各矩形总分平方和最小。

动态规划状态

设 $dp[x_1][y_1][x_2][y_2][k]$ 表示将子矩形 $(x_1,y_1)$ 到 $(x_2,y_2)$ 切割成 $k$ 块矩形的最小平方和。

其中 $(x_1,y_1)$ 是左上角坐标，$(x_2,y_2)$ 是右下角坐标，坐标从 1 开始。

转移方程

1. 如果 $k=1$，那么 $dp[·][·][·][·][1] = (子矩形总分)^2$。
2. 如果 $k>1$，我们需要枚举切割位置和两块分别切割的块数。
   • 横着切：在行 $r$（$x_1 \le r < x_2$）处切成上下两个矩形，上面切成 $t$ 块，下面切成 $k-t$ 块。$$dp = \min_{x_1 \le r < x_2, 1 \le t < k} \left( dp[x_1][y_1][r][y_2][t] + dp[r+1][y_1][x_2][y_2][k-t] \right)$$
   • 竖着切：在列 $c$（$y_1 \le c < y_2$）处切成左右两个矩形，左边切成 $t$ 块，右边切成 $k-t$ 块。$$dp = \min_{y_1 \le c < y_2, 1 \le t < k} \left( dp[x_1][y_1][x_2][c][t] + dp[x_1][c+1][x_2][y_2][k-t] \right)$$

预处理

为了快速计算子矩形的总分，可以预处理二维前缀和 $s[i][j]$，表示从 $(1,1)$ 到 $(i,j)$ 的矩形总分。

子矩形 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的总分为：

$$sum = s[x_2][y_2] - s[x_1-1][y_2] - s[x_2][y_1-1] + s[x_1-1][y_1-1]$$

最终答案

整个棋盘 $(1,1)$ 到 $(8,8)$ 切割成 $n$ 块的最小平方和为 $dp[1][1][8][8][n]$。

最小均方差为：

$$\sigma = \sqrt{ \frac{ dp[1][1][8][8][n] - \frac{sum^2}{n} }{n} }$$

注意：由于 $dp$ 存储的是平方和，而 $\sum x_i^2 = dp[1][1][8][8][n]$，所以 $\sum (x_i - \bar{x})^2 = dp[1][1][8][8][n] - \frac{sum^2}{n}$。

复杂度分析

状态数：$8^4 \times n \approx 4096 \times 14 \approx 57000$。 每个状态转移需要枚举切割位置和分配块数，大约 $O(8 \times n)$。 总计算量大约 $57000 \times 8 \times 14 \approx 6.4 \times 10^6$，可以接受。

注意事项

1. 四舍五入到小数点后三位。
2. 使用 double 类型计算，注意精度。
3. 可以记忆化搜索实现更简洁。
4. 由于 $n < 15$，$k$ 的循环范围要注意。

实现提示

• 使用 memset 初始化 DP 数组为 -1（或极大值），记忆化搜索。
• 计算前缀和便于快速得到矩形总分。
• 最后输出时使用 printf("%.3lf\n", sqrt(...)) 自动四舍五入。