C++(clang++ 11.0.1) 解法, 执行用时: 12ms, 内存消耗: 1908K, 提交时间: 2022-11-21 23:01:47

#include <bits/stdc++.h>
#define sqr(x) ((x)*(x))
using namespace std;
const int N =  17;
int n, m, k;
int a[N][N], s[N][N];
double f[N][N][N][N][N], ave;

double sum(int a, int b, int c, int d){
    return double(s[c][d] - s[a-1][d] - s[c][b-1] + s[a-1][b-1]);
}

double dp(int a, int b, int c, int d, int num){
    if(f[a][b][c][d][num]) return f[a][b][c][d][num];
    else if(num == 1) return sqr(sum(a, b, c, d) - ave);
    f[a][b][c][d][num] = 1e9;
    for(int i = b; i < d; i++)
        for(int j = 1; j < num; j++){
            f[a][b][c][d][num] = min(f[a][b][c][d][num], 
                   dp(a, b, c, i, j) + dp(a, i + 1, c, d, num - j));
        }
    for(int i = a; i < c; i++)
        for(int j = 1; j < num; j++){
            f[a][b][c][d][num]=min(f[a][b][c][d][num],
                    dp(a, b, i, d, j)+dp(i+1, b, c, d, num - j));
        }
    return f[a][b][c][d][num];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            scanf("%d", &a[i][j]);
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    ave = (double) s[n][m] / (double)k;
    printf("%.2lf", sqrt(dp(1, 1, n, m, k) / (double)k));
    
}