#include #include using namespace std; const int N = 9, M = 15; const double INF = 1e8; int n; double f[N][N][N][N][M]; int s[N][N]; //前缀和数组 //获取局部sqrt(x) / n double get(int x1, int y1, int x2, int y2) { double sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]; return sum * sum / n; } double dp(int x1, int y1, int x2, int y2, int k) { double &t = f[x1][y1][x2][y2][k]; if (t) return t; //记忆化搜索 if (k == 1) //不需要再分割 { t = get(x1, y1, x2, y2); return t; } //枚举所有分割方案 t = INF; for (int x = x1; x < x2; x++) //横向切割 { t = min(t, dp(x1, y1, x, y2, 1) + dp(x + 1, y1, x2, y2, k - 1)); t = min(t, dp(x1, y1, x, y2, k - 1) + dp(x + 1, y1, x2, y2, 1)); } for (int y = y1; y < y2; y++) //纵向切割 { t = min(t, dp(x1, y1, x2, y, 1) + dp(x1, y + 1, x2, y2, k - 1)); t = min(t, dp(x1, y1, x2, y, k - 1) + dp(x1, y + 1, x2, y2, 1)); } return t; } int main() { cin >> n; for (int x = 1; x <= 8; x++) for (int y = 1; y <= 8; y++) { cin >> s[x][y]; s[x][y] += s[x - 1][y] + s[x][y - 1] - s[x - 1][y - 1]; } // 这段注释掉 // for (int x1 = 1; x1 <= 8; x1++) // for (int y1 = 1; y1 <= 8; y1++) // for (int x2 = 1; x2 <= 8; x2++) // for (int y2 = 1; y2 <= 8; y2++) // for (int k = 1; k <= n; k++) // f[x1][y1][x2][y2][k] = INF; printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, n) - get(1, 1, 8, 8) / n)); return 0; }