详见代码:
#include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <iostream> #include <algorithm> using namespace std; int N, sum[10][10]; // sum[i][j] 表示以i,j为右下角的矩阵的和 int dp[15][10][10][10][10]; int tot[10][10][10][10]; // tot[m][n][i][j]记录了左上角为m, n右下角为i, j的总和 /* 题目是要求均方差的最小值,我们选择对这个式子进行化简,设均方差为T, 均值为U T^2 = 1/N( sum(xi^2) - U^2 ) 又有 U = sum(xi)/N 可得出答案 因此只要每个部分的和值的平方最小就满足条件了,也就是每一块的和值最小 dp[k][m][n][i][j] 表示左上角为[m, n] 右下角为[i, j]一共有多少种分解方式 那么这个分解方案就是由将这个[m][n][i][j]划出一块了作为第k块,然后将剩下 的一个矩形进行k-1次分割,所以说题目所说的那个剩下的一个矩形也是非常有用的 当横着切的时候 dp[k,m,n,i,j] = min(dp[k-1, m,a,i,j]+tot[m,n,i,a-1], dp[k-1, m,n,i,a-1]+tot[m,a,i,j]); n < a <= j 当竖着切的时候 dp[k,m,n,i,j] = min(dp[k-1, a,n,i,j]+tot[m,n,a-1,j], dp[k-1, m,n,a-1,j]+tot[a,n,i,j]); m < a <= i */ void DP() { for (int k = 1; k < N; ++k) { // 枚举切割了多少次 for (int i = 1; i <= 8; ++i) for (int j = 1; j <= 8; ++j) for (int m = 1; m <= i; ++m) for (int n = 1; n <= j; ++n) { // 枚举合法的四个坐标 // 以下为横向切割 int Min = 0x7fffffff, t; for (int a = n+1; a <= j; ++a) { t = min(dp[k-1][m][a][i][j]+tot[m][n][i][a-1], dp[k-1][m][n][i][a-1]+tot[m][a][i][j]); Min = min(Min, t); } // 以下为纵向切割 for (int a = m+1; a <= i; ++a) { t = min(dp[k-1][a][n][i][j]+tot[m][n][a-1][j], dp[k-1][m][n][a-1][j]+tot[a][n][i][j]); Min = min(Min, t); } if (Min != 0x7fffffff) dp[k][m][n][i][j] = Min; } } } int main() { int c; while (scanf("%d", &N) == 1) { memset(dp, 0x3f, sizeof (dp)); // 没有初始化的话,可能会在动态规划过程中,将一些不可能的值当做0带入进来,比如把一个方格分割成两块 for (int i = 1; i <= 8; ++i) { for (int j = 1; j <= 8; ++j) { scanf("%d", &sum[i][j]); sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]; } } for (int i = 1; i <= 8; ++i) for (int j = 1; j <= 8; ++j) for (int m = 1; m <= i; ++m) for (int n = 1; n <= j; ++n) { tot[m][n][i][j] = sum[i][j] - sum[m-1][j] - sum[i][n-1] + sum[m-1][n-1]; tot[m][n][i][j] *= tot[m][n][i][j]; // 计算出子矩形和的平方 dp[0][m][n][i][j] = tot[m][n][i][j]; // 边界条件的初始化 } DP(); printf("%.3lf\n", sqrt(double(N*dp[N-1][1][1][8][8]-tot[1][1][8][8])/(N*N))); } return 0; }