题意：将一个８*８的棋盘（每个单元正方形有个分值）沿直线（竖或横）割掉一块，留下一块，对留下的这块继续这样操作，总共进行n - 1次，得到n块(1 < n < 15)矩形，每个矩形的分值就是单元正方形的分值的和，问这n个矩形的最小均方差。
题目链接：http://poj.org/problem?id=1191
——>>此题中，均方差比较，等价于方差比较，等价于平方和比较。。
状态：dp[x1][y1][x2][y2][i]表示将(x1, y1)到(x2, y2)的矩形分割i次的最小平方和。
状态转移方程：dp[x1][y1][x2][y2][i] = min(dp[x1][y1][j][y2][i - 1] + nSquare[j + 1][y1][x2][y2], dp[j + 1][y1][x2][y2][i - 1] + nSquare[x1][y1][j][y2], );（水平方向切割）
dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][j][i - 1] + nSquare[x1][j + 1][x2][y2], dp[x1][j + 1][x2][y2][i - 1] + nSquare[x1][y1][x2][j]);（竖直方向切割）
两个方向再取最小值。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using std::sqrt;
using std::min;const int WIDTH = 8;
const int MAXN = 15 + 1;
const int INF = 0x3f3f3f3f;int a[WIDTH + 1][WIDTH + 1];
int nSum[WIDTH + 1][WIDTH + 1][WIDTH + 1][WIDTH + 1];
int nSquare[WIDTH + 1][WIDTH + 1][WIDTH + 1][WIDTH + 1];
int dp[WIDTH + 1][WIDTH + 1][WIDTH + 1][WIDTH + 1][MAXN];void Init()
{memset(nSum, 0, sizeof(nSum));for (int x1 = 1; x1 <= WIDTH; ++x1){for (int y1 = 1; y1 <= WIDTH; ++y1){for (int x2 = x1; x2 <= WIDTH; ++x2){for (int y2 = y1; y2 <= WIDTH; ++y2){nSum[x1][y1][x2][y2] = nSum[x1][y1][x2 - 1][y2] + nSum[x1][y1][x2][y2 - 1] - nSum[x1][y1][x2 - 1][y2 - 1] + a[x2][y2];nSquare[x1][y1][x2][y2] = nSum[x1][y1][x2][y2] * nSum[x1][y1][x2][y2];dp[x1][y1][x2][y2][0] = nSquare[x1][y1][x2][y2];}}}}
}void Dp(int n)
{for (int i = 1; i <= n - 1; ++i){for (int x1 = WIDTH; x1 >= 1; --x1){for (int y1 = 1; y1 <= WIDTH; ++y1){for (int x2 = x1; x2 <= WIDTH; ++x2){for (int y2 = y1; y2 <= WIDTH; ++y2){dp[x1][y1][x2][y2][i] = INF;for (int j = x1; j < x2; ++j){dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][y2][i], dp[x1][y1][j][y2][i - 1] + nSquare[j + 1][y1][x2][y2]);dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][y2][i], dp[j + 1][y1][x2][y2][i - 1] + nSquare[x1][y1][j][y2]);}for (int j = y1; j < y2; ++j){dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][y2][i], dp[x1][y1][x2][j][i - 1] + nSquare[x1][j + 1][x2][y2]);dp[x1][y1][x2][y2][i] = min(dp[x1][y1][x2][y2][i], dp[x1][j + 1][x2][y2][i - 1] + nSquare[x1][y1][x2][j]);}}}}}}
}void Output(int n)
{double fAvg = 1.0 * nSum[1][1][8][8] / n;printf("%.3f\n", sqrt(1.0 * dp[1][1][8][8][n - 1] / n - fAvg * fAvg));
}void Read()
{for (int i = 1; i <= WIDTH; ++i){for (int j = 1; j <= WIDTH; ++j){scanf("%d", &a[i][j]);}}
}int main()
{int n;while (scanf("%d", &n) == 1){Read();Init();Dp(n);Output(n);}return 0;
}