思路:
记忆化搜索
DP分析:
参考题解: https://www.acwing.com/solution/content/62836/
时间复杂度:$O(N^5)$。
由于会频繁地计算某个子矩阵的方差,因此我们需要预先处理出前缀和,保证计算方差的时间复杂度为 O(1)
import java.io.*;
import java.util.*;
public class Main {
static int N = 15, M = 10;
static double INF = 1e9, X; // X为平均值X拔
static int[][] s = new int[M][M]; // 矩阵前缀和
// f[x1,y1,x2,y2,k]表示左上角(x1,y1)到右下角(x2,y2)切分k次的σ最小值
static double[][][][][] f = new double[M][M][M][M][N];
static 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];
sum = sum - X;
return sum * sum;
}
public static double dp(int x1, int y1, int x2, int y2, int k) {
double v = f[x1][y1][x2][y2][k];
if (v >= 0) return v; // 记忆化搜索,直接返回已经计算的结果
if (k == 1) return v = get(x1, y1, x2, y2);
v = INF;
for (int i = x1; i < x2; i++) { // 横着切
v = Math.min(v, dp(x1, y1, i, y2, k - 1) + get(i + 1, y1, x2, y2)); // 对上半部dp + 下半部求(xi - X拔)^2
v = Math.min(v, dp(i + 1, y1, x2, y2, k - 1) + get(x1, y1, i, y2)); // 对下半部dp + 上半部求(xi - X拔)^2
}
for (int j = y1; j < y2; j++) { // 竖着切
v = Math.min(v, dp(x1, y1, x2, j, k - 1) + get(x1, j + 1, x2, y2)); // 对左半部dp + 右半部求(xi - X拔)^2
v = Math.min(v, dp(x1, j + 1, x2, y2, k - 1) + get(x1, y1, x2, j)); // 对右半部dp + 左半部求(xi - X拔)^2
}
return f[x1][y1][x2][y2][k] = v;
}
public static void main(String[] args) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int k = Integer.parseInt(br.readLine()); // 切分多少次
String[] s1;
for (int i = 1; i <= 8; i++) {
s1 = br.readLine().split(" ");
for (int j = 1; j <= 8; j++) {
s[i][j] = Integer.parseInt(s1[j - 1]);
// 子矩阵和: 先加后减
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
// 痛苦java
for (int a = 0; a < M; a++)
for (int b = 0; b < M; b++)
for (int c = 0; c < M; c++)
for (int d = 0; d < M; d++)
Arrays.fill(f[a][b][c][d], -1);
X = (double) s[8][8] / k; // X拔跟切多少块有关
double sqrt = Math.sqrt(dp(1, 1, 8, 8, k) / k); // 跟n有关系
bw.write(String.format("%.3f", sqrt) + "\n");
bw.flush();
}
}