不錯(cuò)的DP題。狀態(tài)f[i][x1][y1][x2][y2]表示要把(x1,y1) -- (x2, y2) 分割成i塊所得到的最小平方和（平方和指的是每塊矩形的和的平方和）。然后根據(jù)水平和豎直切割進(jìn)行狀態(tài)轉(zhuǎn)移。這樣計(jì)算出f[n][1][1][8][8]得到整個(gè)棋盤(pán)分割成n塊得到的最小平方和，然后代入均方差公式算得結(jié)果。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-10-1 19:01:11
File Name: pku1191.cpp
Description:
************************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
int n;
int a[9][9], g[9][9];
int f[16][9][9][9][9];
inline int sum(int x1, int y1, int x2, int y2)
{
return (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1])
* (g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1]);
}
int dp(int k, int x1, int y1, int x2, int y2)
{
if (f[k][x1][y1][x2][y2] != maxint)
return f[k][x1][y1][x2][y2];
if (k == 1)
return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
if (x1 == x2 && y1 == y2)
return f[k][x1][y1][x2][y2] = sum(x1, y1, x2, y2);
int ret = maxint;
for (int i = x1; i < x2; i++)
{
ret <?= dp(k - 1, x1, y1, i, y2) + sum(i + 1, y1, x2, y2);
ret <?= sum(x1, y1, i, y2) + dp(k - 1, i + 1, y1, x2, y2);
}
for (int i = y1; i < y2; i++)
{
ret <?= dp(k - 1, x1, y1, x2, i) + sum(x1, i + 1, x2, y2);
ret <?= sum(x1, y1, x2, i) + dp(k - 1, x1, i + 1, x2, y2);
}
return f[k][x1][y1][x2][y2] = ret;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++)
scanf("%d", &a[i][j]);
memset(g, 0, sizeof(g));
for (int i = 0; i <= 8; i++)
for (int j = 0; j <= 8; j++)
g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + a[i][j];
for (int k = 0; k <= 15; k++)
for (int x1 = 1; x1 <= 8; x1++)
for (int y1 = 1; y1 <= 8; y1++)
for (int x2 = 1; x2 <= 8; x2++)
for (int y2 = 1; y2 <= 8; y2++)
f[k][x1][y1][x2][y2] = maxint;
double sum = 0.0;
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++)
sum += a[i][j];
sum /= n;
sum *= sum;
printf("%.3lf\n", sqrt(dp(n, 1, 1, 8, 8) / double(n) - sum));
return 0;
}