记忆化搜索

import java.util.*;
class Main{
    private static int n, m = 8;
    private static double X, inf = 1e9;
    private static int[][] s;
    private static double[][][][][] f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = new int[m+1][m+1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= m; j++){
                s[i][j] = sc.nextInt();
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            }
        }
        X = (double) s[m][m] / n;
        f = new double[m+1][m+1][m+1][m+1][n+1];
        for(int i1 = 0; i1 <= m; i1++){
            for(int j1 = 0; j1 <= m; j1++){
                for(int i2 = 0; i2 <= m; i2++){
                    for(int j2 = 0; j2 <= m; j2++){
                        for(int k = 0; k <= n; k++){
                            f[i1][j1][i2][j2][k] = -inf;
                        }
                    }
                }
            }
        }
        System.out.println(String.format("%.3f", Math.sqrt(dp(1, 1, m, m, n))));
    }
    private static double dp(int x1, int y1, int x2, int y2, int k){
        double t = f[x1][y1][x2][y2][k];
        if(t >= 0) return t;
        if(k == 1){
             t = get(x1, y1, x2, y2);
             f[x1][y1][x2][y2][k] = t;
             return t;
        }
        t = inf;
        for(int i = x1; i < x2; i++){
            t = Math.min(t, dp(x1, y1, i, y2, k - 1) + get(i+1, y1, x2, y2));
            t = Math.min(t, dp(i+1, y1, x2, y2, k-1) + get(x1, y1, i, y2));
        }
        for(int j = y1; j < y2; j++){
            t = Math.min(t, dp(x1, y1, x2, j, k-1) + get(x1, j+1, x2, y2));
            t = Math.min(t, dp(x1, j+1, x2, y2, k-1) + get(x1, y1, x2, j));
        }
        f[x1][y1][x2][y2][k] = t;
        return t;
    }
    private 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] - X;
        return (double) (sum * sum) / n;
    }
}