#include using namespace std; const int N = 9, M = 15; const double INF = 0x3f3f3f3f; double s[N][N]; // 矩阵前缀和 int n; int m = 8; double f[N][N][N][N][M]; double get(int x1, int y1, int x2, int y2) { double X = s[m][m] / n; double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]; sum = sum - X; return sum * sum / n; } void init() { for (int k = 0; k < M; k++) // 注意先枚举剩余刀数 for (int x1 = 1; x1 <= 8; x1++) for (int y1 = 1; y1 <= 8; y1++) for (int x2 = x1; x2 <= 8; x2++) for (int y2 = y1; y2 <= 8; y2++) if (k) f[x1][y1][x2][y2][k] = INF; // 其他状态都没有到达 else f[x1][y1][x2][y2][k] = get(x1, y1, x2, y2); // 切割0次 } int main() { scanf("%d", &n); for (int i = 1; i <= 8; i++) for (int j = 1; j <= 8; j++) { scanf("%lf", &s[i][j]); s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]; } init(); // k的含义是剩余的刀数,为阶段概念,需要写在外层循环 for (int k = 1; k < n; k++) for (int x1 = 1; x1 <= 8; x1++) for (int y1 = 1; y1 <= 8; y1++) for (int x2 = x1; x2 <= 8; x2++) for (int y2 = y1; y2 <= 8; y2++) { double &v = f[x1][y1][x2][y2][k]; // 横切 for (int i = x1; i < x2; i++) { v = min(v, f[x1][y1][i][y2][k - 1] + get(i + 1, y1, x2, y2)); // 选上边,加下面 v = min(v, f[i + 1][y1][x2][y2][k - 1] + get(x1, y1, i, y2)); // 选下边 } // 纵切 for (int i = y1; i < y2; i++) { v = min(v, f[x1][y1][x2][i][k - 1] + get(x1, i + 1, x2, y2)); // 选左边,加右边 v = min(v, f[x1][i + 1][x2][y2][k - 1] + get(x1, y1, x2, i)); // 选右边 } } printf("%.3f\n", sqrt(f[1][1][8][8][n - 1])); return 0; }