C++语言: 高亮代码由发芽网提供

//头文件 宏定义省略
int array[10][10];
int dp[10][10];
int dp_sum[10][10][10][10];
int dfs_num[16][10][10][10][10];
int dfs(int k,int i,int j,int r,int s){
    //dp2[k][i][j][r][s] = min{
    //min{dp2[k-1][i][j][a][s] + S[a+1][j][r][s],dp2[k-1][a+1][j][r][s] + S[i][j][a][s]},//i<=a < r
    //min{dp2[k-1][i][j][r][b] + S[i][b+1][r][s],dp2[k-1][i][b+1][r][s] + S[i][j][r][b]}//j <= b < s
    //}
    if(dfs_num[k][i][j][r][s] != -1)return dfs_num[k][i][j][r][s];
    if(k == 0){
        if(dp_sum[i][j][r][s] == -1){
            int t = dp[r][s] + dp[i-1][j-1] - dp[r][j-1] - dp[i-1][s];
            dp_sum[i][j][r][s] = t*t;
        }
        return dp_sum[i][j][r][s];
    }
    int min = INF;
    for(int a = i;a < r;a++){
        if(dp_sum[a+1][j][r][s] == -1){
            int S1 = dp[r][s] + dp[a][j-1] - dp[r][j-1] - dp[a][s];
            dp_sum[a+1][j][r][s] = S1*S1;
        }
        if(dp_sum[i][j][a][s] == -1){
            int S2 = dp[a][s] + dp[i-1][j-1] - dp[a][j-1] - dp[i-1][s];
            dp_sum[i][j][a][s] = S2*S2;
        }
        min = mymin(min,mymin(dfs(k-1,i,j,a,s)+dp_sum[a+1][j][r][s],dfs(k-1,a+1,j,r,s)+dp_sum[i][j][a][s]));
    }
    for(int b = j;b < s;b++){
        if(dp_sum[i][b+1][r][s] == -1){
            int S1 = dp[r][s] + dp[i-1][b] - dp[r][b] - dp[i-1][s];
            dp_sum[i][b+1][r][s] = S1*S1;
        }
        if(dp_sum[i][j][r][b]){
            int S2 = dp[r][b] + dp[i-1][j-1] -dp[r][j-1] - dp[i-1][b];
            dp_sum[i][j][r][b] = S2*S2;
        }
        min = mymin(min,mymin(dfs(k-1,i,j,r,b)+dp_sum[i][b+1][r][s],dfs(k-1,i,b+1,r,s)+dp_sum[i][j][r][b]));
    }
    return dfs_num[k][i][j][r][s] = min;
}
int main(){
    int N;scanf("%d",&N);
    for(int i = 1;i <= 8;i++){
        for(int j = 1;j <= 8;j++){
            scanf("%d",&array[i][j]);
        }
    }
    memset(dp,0,sizeof(dp));
    memset(dp_sum,-1,sizeof(dp_sum));
    memset(dfs_num,-1,sizeof(dfs_num));
    dp[1][1] = array[1][1];
    for(int i = 2;i <= 8;i++){
        dp[1][i] = dp[1][i-1] + array[1][i];
        dp[i][1] = dp[i-1][1] + array[i][1];
    }
    for(int i = 2;i <= 8;i++){
        for(int j = 2;j <= 8;j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + array[i][j];
        }
    }
    printf("%0.3f",sqrt((N*dfs(N-1,1,1,8,8)-dp[8][8]*dp[8][8])*1.0/N/N));
    return 0;
}