You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
67 lines
1.7 KiB
67 lines
1.7 KiB
#include <iostream>
|
|
#include <cmath>
|
|
|
|
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;
|
|
}
|