【题目链接】
点击打开链接【思路要点】
平均值可以先求出来。记\(F_{lx,ly,rx,ry,cnt}\)表示将左上角为\((lx,ly)\)，右上角为\((rx,ry)\)矩阵分成\(cnt\)份，各份的最小标准差之和的值。预处理二维前缀和，记忆化搜索即可。时间复杂度\(O((A+B)A^2B^2N^2)\)。【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 15 template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } int n, m, k; int value[MAXN][MAXN], sum[MAXN][MAXN]; bool visited[MAXN][MAXN][MAXN][MAXN][MAXN]; double dp[MAXN][MAXN][MAXN][MAXN][MAXN], aver; int query(int lx, int ly, int rx, int ry) { return sum[rx][ry] - sum[lx - 1][ry] - sum[rx][ly - 1] + sum[lx - 1][ly - 1]; } double sqr(double value) { return value * value; } double get(int lx, int ly, int rx, int ry, int cnt) { if (visited[lx][ly][rx][ry][cnt]) return dp[lx][ly][rx][ry][cnt]; if (cnt == 1) return sqr(query(lx, ly, rx, ry) - aver); double tans = 1e12; for (int i = lx; i < rx; i++) for (int j = 1; j < cnt; j++) tans = min(tans, get(lx, ly, i, ry, j) + get(i + 1, ly, rx, ry, cnt - j)); for (int i = ly; i < ry; i++) for (int j = 1; j < cnt; j++) tans = min(tans, get(lx, ly, rx, i, j) + get(lx, i + 1, rx, ry, cnt - j)); visited[lx][ly][rx][ry][cnt] = true; return dp[lx][ly][rx][ry][cnt] = tans; } int main() { read(n), read(m), read(k); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { read(value[i][j]); sum[i][j] = value[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1]; } aver = (double) sum[n][m] / k; printf("%.2lf\n", sqrt(get(1, 1, n, m, k) / k)); return 0; }