题意：中文题，感觉没什么好翻译的。http://poj.org/problem?id=1191
解法：将均方差公式变形，用ave表示平均值，均方差 = (∑xi*xi - 2 * ave * ∑xi + n * ave * ave) / n = (∑xi*xi - n*ave*ave)/n。由于平均数一定，所以只需要使平方之和最小即可。
设s[x1][y1][x2][y2]表示以(x1, y1)为左上角，以(x2, y2)为右下角的矩形里，所有小格的数之和的平方。d[t][x1][y1][x2][y2]表示切t刀，以(x1, y1)为左上角，以(x2, y2)为右下角的矩形所能参生的最小平方和是多少。
tag：dp
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-11-17 19:22 4 * File Name: DP-POJ-1191.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <cmath> 10 11 using namespace std; 12 13 #define CLR(x) memset(x, 0, sizeof(x)) 14 const int maxint = 2147483647; 15 16 int n; 17 double sum; 18 int d[20][10][10][10][10]; 19 int a[10][10], ss[10][10][10][10], s[10][10][10][10]; 20 21 void init() 22 { 23 sum = 0.0; 24 for (int i = 1; i <= 8; ++ i) 25 for (int j = 1; j <= 8; ++ j){ 26 scanf ("%d", &a[i][j]); 27 sum += a[i][j]; 28 } 29 30 CLR (ss); 31 for (int i = 1; i <= 8; ++ i) 32 for (int j = 1; j <= 8; ++ j) 33 for (int k = i; k <= 8; ++ k) 34 for (int l = j; l <= 8; ++ l){ 35 if (i == k && j == l) 36 ss[i][j][k][l] = a[i][j]; 37 else if (j == l) 38 ss[i][j][k][l] = ss[i][j][k-1][l] + a[k][l]; 39 else{ 40 ss[i][j][k][l] = ss[i][j][k][l-1]; 41 for (int ii = i; ii <= k; ++ ii) 42 ss[i][j][k][l] += a[ii][l]; 43 } 44 } 45 46 CLR (s); 47 for (int i = 1; i <= 8; ++ i) 48 for (int j = 1; j <= 8; ++ j) 49 for (int k = i; k <= 8; ++ k) 50 for (int l = j; l <= 8; ++ l) 51 s[i][j][k][l] = ss[i][j][k][l]*ss[i][j][k][l]; 52 } 53 54 double gao() 55 { 56 for (int i = 1; i <= 8; ++ i) 57 for (int j = 1; j <= 8; ++ j) 58 for (int k = i; k <= 8; ++ k) 59 for (int l = j; l <= 8; ++ l) 60 d[1][i][j][k][l] = s[i][j][k][l]; 61 62 for (int t = 2; t <= n; ++ t) 63 for (int i = 1; i <= 8; ++ i) 64 for (int j = 1; j <= 8; ++ j) 65 for (int k = i; k <= 8; ++ k) 66 for (int l = j; l <= 8; ++ l){ 67 if (i == k && j == l){ 68 d[t][i][j][k][l] = s[i][j][k][l]; 69 continue; 70 } 71 int tmp = maxint; 72 for (int a = i; a < k; ++ a){ 73 tmp = min(tmp, d[t-1][i][j][a][l] + s[a+1][j][k][l]); 74 tmp = min(tmp, d[t-1][a+1][j][k][l] + s[i][j][a][l]); 75 } 76 for (int a = j; a < l; ++ a){ 77 tmp = min(tmp, d[t-1][i][j][k][a] + s[i][a+1][k][l]); 78 tmp = min(tmp, d[t-1][i][a+1][k][l] + s[i][j][k][a]); 79 } 80 d[t][i][j][k][l] = tmp; 81 } 82 83 double ret = (double)d[n][1][1][8][8] / n - (sum*sum/n/n); 84 ret = sqrt(ret); 85 return ret; 86 } 87 88 int main() 89 { 90 while (scanf ("%d", &n) != EOF){ 91 init(); 92 printf ("%.3f ", gao()); 93 } 94 return 0; 95 }