将一个 $a \times b$ 的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割 (当然也可以只分割其中的一个)，这样分割了 $n-1$ 次后，原矩阵被分割成了 $n$ 个矩阵。(注：每次分割都只能沿着数字间的缝隙进行)
原矩阵中每一位置上有一个分值，一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成 $n$ 个矩阵，并使各矩阵总分的均(biao)方(zhun)差最小。请编程对给出的矩阵及 $n$，求出均(biao)方(zhun)差的最小值。
第一行包含三个正整数 $a, b, n$ ($a, b, n \leq 10$)。
接下来的 $n$ 行，每行包含 $b$ 个小于 $100$ 的非负整数，表示矩阵中相应位置上的分值。每行相邻两数之间用一个空格分开。
输出一行一个实数，表示均方差的最小值 (四舍五入精确到小数点后 $2$ 位)。
Q：均方差是什么？A：标准差的别名~(所以最后不要忘记开根号)
由方差的公式 $D(X) = \dfrac 1n \left( E(X^2) - (E(X))^2 \right)$，又发现 $E(X)$ 即所有矩阵总分的平均数，等于所有矩阵总分的和除以矩阵个数 $n$，发现恰好是个常数 (可以预处理出来)。
于是让 $D(X)$ 最小只需让 $E(X^2)$ 最小，而它就是所有矩阵总分的平方和。
注意到 $n$ 并不是很大，因此可以考虑最暴力的 DP：记 $f_{r_1, c_1, r_2, c_2, k}$ 表示原矩阵的 $(r_1, c_1)$ 到 $(r_2, c_2)$ 的子矩阵中，分成 $k$ 块的平方和的最小值，那么有边界 $k = 1$ 时就是这个子矩阵的总分的平方，答案就是 $f_{1, 1, a, b, n}$。
然而这个不太好转移 (一是 for 循环太多，二是速度太慢)，因此可以考虑使用记忆化搜索，每次考虑按行割或按列割，再枚举两边还要分割成多少个矩阵，最后再取个 $\min$。
当然，当 $k = 1$ 时，这个边界可以通过二维前缀和预处理出来。最后由开头提到的公式，直接算出标准差即可。时间复杂度大概就 $n$ 的五六次左右，还是比较小的。
#include <bits/stdc++.h>
#define N 12
using namespace std;
int r, c, n, i, j, t;
int s[N][N];
double f[N][N][N][N][N];
double average, avrQuad;
inline void down(double &x, const double y) {x > y ? x = y : 0;}
double dp(int r1, int c1, int r2, int c2, int k){
int r0, c0, i;
double &ret = f[r1][c1][r2][c2][k];
if(ret == ret) return ret; // ret isn't NaN
if(k == 1){
int s0 = s[r2][c2] - s[r2][c1 - 1] - s[r1 - 1][c2] + s[r1 - 1][c1 - 1];
return ret = (double)(s0 * s0);
}
ret = INFINITY;
for(i = 1; i < k; ++i){
for(r0 = r1; r0 < r2; ++r0) down(ret, dp(r1, c1, r0, c2, i) + dp(r0 + 1, c1, r2, c2, k - i));
for(c0 = c1; c0 < c2; ++c0) down(ret, dp(r1, c1, r2, c0, i) + dp(r1, c0 + 1, r2, c2, k - i));
}
return ret;
}
int main(){
scanf("%d%d%d", &r, &c, &n);
for(i = 1; i <= r; ++i)
for(j = 1; j <= c; ++j){
scanf("%d", &t);
s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + t;
}
memset(f, -1, sizeof f); // fill NaN to f[]
average = (double)s[r][c] / (double)n;
avrQuad = dp(1, 1, r, c, n) / (double)n;
// D(X) = (E(X^2) - E^2(X))/n, sigma(X) = sqrt(D(X))
printf("%.2lf\n", sqrt(avrQuad - average * average));
return 0;
}
浮点数预处理这东西没有必要写一个笨拙的五重循环，可以使用神奇的 memset() 方法。比如说将浮点数组 f[] 进行 memset(f, 127, sizeof f) 后就得到了非常大的数 (1.38e306，但不是 inf)，将 f[] 进行 memset(f, -1, sizeof f) 后就可以得到 nan。
然后就可以利用 inf 或 nan 来判断是否搜索到过，比如说本题代码就是用了 ret == ret 来判断它是不是 nan。
坑1：然后就是可以使用数组引用，减少高维数组的寻址来减少常数。