Description
将一个\(a * b\)的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割（当然也可以只分割其中的一个），这样分割了\((n - 1)\)次后，原矩阵被分割成了\(n\)个矩阵。（每次分割都只能沿着数字间的缝隙进行）原矩阵中每一位置上有一个分值,一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成\(n\)个矩阵，并使各矩阵总分的均方差最小。请编程对给出的矩阵及\(n\)，求出均方差的最小值。
Solution
最近怎么做了这么多蛤省河南省的题啊。
#include#include #include #include #include #include #include #include using namespace std;#define rep(i, a, b) for (int i = a; i <= b; i++)#define drp(i, a, b) for (int i = a; i >= b; i--)#define fech(i, x) for(int i = 0; i < x.size(); i++)#define N 15inline int read() { int x = 0, flag = 1; char ch = getchar(); while (ch > '9' || ch < '0') { if (ch == '-') flag = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * flag;}inline void write(int x) { if (x >= 10) write(x / 10); putchar(x % 10 + '0'); }double f[N][N][N][N][N];int s[N][N];double ba;double dfs(int a, int b, int c, int d, int k) { double tmp; if (f[a][b][c][d][k] != -1) return f[a][b][c][d][k]; if (k == 1) { tmp = s[c][d] + s[a - 1][b - 1] - s[c][b - 1] - s[a - 1][d]; return f[a][b][c][d][k] = (tmp - ba) * (tmp - ba); } int i, j; tmp = 1e9; rep(i, a, c - 1) rep(j, 1, k - 1) tmp = min(tmp, dfs(a, b, i, d, j) + dfs(i + 1, b, c, d, k - j)); rep(i, b, d - 1) rep(j, 1, k - 1) tmp = min(tmp, dfs(a, b, c, i, j) + dfs(a, i + 1, c, d, k - j)); return f[a][b][c][d][k] = tmp;}int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); rep(i, 1, n) rep(j, 1, m) s[i][j] = read() + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; rep(a, 0, n + 1) rep(b, 0, m + 1) rep(c, 0, n + 1) rep(d, 0, m + 1) rep(t, 0, k + 1) f[a][b][c][d][t] = -1; ba = (double)s[n][m] / k; printf("%.2f", sqrt(dfs(1, 1, n, m, k) / k)); return 0;}