思路分析

本题属于矩阵类的区间dp，和多边形的类似，都是枚举切割成两个部分的那条线

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 16, M = 9;
const double INF = 1e9;

int sum[N][N];
int n, m = 8;
double memo[M][M][M][M][N];
double X;

int get_sum(int x1, int y1, int x2, int y2){
    return sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
}

double get(int x1, int y1, int x2, int y2){
    double s = get_sum(x1, y1, x2, y2) - X;
    return (double)s * s / n;
}

double dfs(int x1, int y1, int x2, int y2, int k){
    double& val = memo[x1][y1][x2][y2][k];
    if(val >= 0) return val;
    if(k == 1) return val = get(x1, y1, x2, y2);
    val = INF;
    //枚举横着的分割线
    for(int i = x1;i < x2;++i){
        val = min(val, get(x1, y1, i, y2) + dfs(i+1, y1, x2, y2, k - 1));
        val = min(val, get(i+1, y1, x2, y2) + dfs(x1, y1, i, y2, k - 1));
    }
    //枚举竖着的分割线
    for(int i = y1;i < y2;++i){
        val = min(val, get(x1, y1, x2, i) + dfs(x1, i+1, x2, y2, k - 1));
        val = min(val, get(x1, i+1, x2, y2) + dfs(x1, y1, x2, i, k - 1));
    }
    return val;
}

int main(){
    cin >> n;
    for(int i = 1;i <= m;++i)
        for(int j = 1;j <= m;++j){
            cin >> sum[i][j];
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
        }
    X = (double)sum[m][m] / n;
    memset(memo, -1, sizeof memo);
    printf("%.3lf", sqrt(dfs(1, 1, 8, 8, n)));
    return 0;
}