//592K 32MS C++
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
long DP[16][9][9][9][9];
int chess[8][8];
long getSquareSum(int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 < y2) {
return 0;
}
long sum = 0;
for (int i = y2; i <= y1; i++) {
for (int j = x1; j <= x2; j++) {
sum += chess[j][i];
}
}
return sum*sum;
}
int N;
#define INF 99999999
inline long min(long a, long b) {
return a < b ? a: b;
}
long totalSum;
void getMin() {
memset(DP, 0, sizeof(DP));
for (int k = 1; k <= N; k++) {
for (int x1 = 0; x1 <= 7; x1++) {
for (int y1 = 0; y1 <= 7; y1++) {
for (int x2 = 0; x2 <= 7; x2++) {
for (int y2 = 0; y2 <= 7; y2++) {
if (k == 1) {
DP[k][x1][y1][x2][y2] = getSquareSum(x1, y1, x2, y2);
} else if (x2 == x1 && y1 == y2) {// impossible to cut to k parts
// printf("%d %d %d %d %d\n", k, x1, y1, x2, y2);
DP[k][x1][y1][x2][y2] = INF;
// } else if (x2 - x1 + 1 >= k && y1 - y2 + 1 < k) { // only can cut x
// DP[k][x1][y1][x2][y2] = INF;
// for (int cutPos = x1; cutPos <= x2; cutPos++) {
// long chose1 = getSquareSum(x1,y1, cutPos, y2) + DP[k-1][cutPos+1][y1][x2][y2];
// long chose2 = getSquareSum(cutPos+1, y1, x2, y2) + DP[k-1][x1][y1][cutPos][y2];
// long tmp = min(chose1, chose2);
// DP[k][x1][y1][x2][y2] = min(tmp, DP[k][x1][y1][x2][y2]);
// }
// } else if (x2 - x1 < k && y1 - y2 >= k) { // only can cut y
// DP[k][x1][y1][x2][y2] = INF;
// for (int cutPos = y2; cutPos <= y1; cutPos++) {
// long chose1 = getSquareSum(x1, y1, x2, cutPos) + DP[k-1][x1][cutPos-1][x2][y2];
// long chose2 = getSquareSum(x1, cutPos-1, x2, y2) + DP[k-1][x1][y1][x2][cutPos];
// long tmp = min(chose1, chose2);
// DP[k][x1][y1][x2][y2] = min(tmp, DP[k][x1][y1][x2][y2]);
// }
} else {
DP[k][x1][y1][x2][y2] = INF;
for (int cutPos = x1; cutPos <= x2; cutPos++) {
long chose1 = getSquareSum(x1,y1, cutPos, y2) + DP[k-1][cutPos+1][y1][x2][y2];
long chose2 = getSquareSum(cutPos+1, y1, x2, y2) + DP[k-1][x1][y1][cutPos][y2];
long tmp = min(chose1, chose2);
DP[k][x1][y1][x2][y2] = min(tmp, DP[k][x1][y1][x2][y2]);
}
for (int cutPos = y2; cutPos <= y1; cutPos++) {
long chose1 = getSquareSum(x1, y1, x2, cutPos) + DP[k-1][x1][cutPos-1][x2][y2];
long chose2 = getSquareSum(x1, cutPos-1, x2, y2) + DP[k-1][x1][y1][x2][cutPos];
long tmp = min(chose1, chose2);
DP[k][x1][y1][x2][y2] = min(tmp, DP[k][x1][y1][x2][y2]);
}
}
}
}
}
}
}
// printf("%ld %ld\n", DP[N][0][7][7][0], DP[1][0][7][7][0]);
// printf("%ld\n", DP[N][0][7][7][0]);
double ans=sqrt(DP[N][0][7][7][0]*1.0/N-((totalSum*1.0)/N*(totalSum*1.0)/N));
printf("%.3f\n", ans);
}
int main() {
scanf("%d", &N);
totalSum = 0;
for (int i = 0; i <= 7; i++) {
for (int j = 0; j <= 7; j++) {
scanf("%d", &chess[j][i]);
// printf("%d\n", chess[j][i]);
totalSum += chess[j][i];
}
}
getMin();
}转化稍微有些难度，主要是要将方程变下形，然后才能看出来：
S^2 = 1/n *（∑(Xi - X)^2）
= 1/n(n*X^2 + ∑Xi^2 - 2*X∑Xi)
= 1/n（∑Xi^2） - X^2
这里的Xi是每个切割出来的矩形的矩形和，X是整个大矩形的矩形和/(8*8) , X 在输入完数据以后就确定了， 那么 为了使S尽量小，就要尽量使Xi(1~N)的平方和 的和 尽量小了，
一个重要的理解是，题目最后要得到N个矩形， 那么一共要切 N - 1刀， 注意的是，一个矩形被从大矩形切出来以后，就不能再被切割了，而是作为最后的N个矩形中的一块存在，这一点很重要，否则，如果之前切出来的矩阵也可以被切，就得不到下面的状态方程了：
DP[K][x1][y1][x2][y2]:
指的是对于 左上角是(x1, y1), 右下角是(x2, y2)的矩阵部分进行切割，得到K块 子矩阵时， K个矩阵的矩阵和的平方的和的最小值，
那么显然，题目要求其实就是 DP[N][0][8][8][0]这个值，
递归如下：
<case 1>: 如果K== 1, 那么不需要再切割，只有一个矩阵， 直接返回(x1, y1, x2, y2)所代表的矩阵和的平方即可。
<case 2>: 如果 K >1, 但是此时 x1 == x2, y1 = y2, 即只剩下一个单位块了，不可能再分割，这种无效情况，设为INF（无穷大，因为本题要的是极小值，所以INF代表无效情况）
自己刚开始2B了，code注释掉的那一段就是没想清楚，把有些有效情况也给无效化了.
<case 3>: 如果可以分割， 那么就从当前的矩阵割下一块，这一刀一共有 (x2 - x1 + y1 - y2 )种割法， 分别对应矩阵内部的每一条与x轴平行或与y轴平行的线，而在切完以后，
当前矩阵变成了两部分，A和B，而这时候还有两种选择： 继续切割A 或者 继续切割B， DP在此时的取值就是这么多分支情况中，那个矩阵和的平方的和最小的值。
dp[k,x1,y1,x2,y2] =min{
min{dp[k-1,x1,y1,a,y2]+S[a+1,y1,x2,y2] , dp[k-1,a+1,y1,x2,y2]+S[x1,y1,a,y2]}(x1<=a<x2),
min{dp[k-1,x1,y1,x2,b]+S[x1,b+1,x2,y2] , dp[k-1,x1,b+1,x2,y2]+S[x1,y1,x2,b]}(y1<=b<y2)
}最后DP的5重循环完了以后，就可以带入公式计算最终值了， .3f输出.
一开始还准备将矩阵先预处理一下，得到从(0,0)到各个点的矩阵和， 这样在后方要得到(x1, y1) 到 (x2, y2)的矩阵和的时候会快点，但是看到矩阵只有8*8， 因此直接野蛮了一把，也过了.