【Luogu P5752】[NOI1999] 棋盘分割
链接：
题目大意：
将一个 8 \(\times\) 8 的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了 \((n-1)\) 次后，连同最后剩下的矩形棋盘共有 \(n\) 块矩形棋盘。 (每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 \(n\) 块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差 \(\sigma = \sqrt{ \frac{ \sum_{i=1}^n (x_i - \bar x)^2 } { n }}\)，其中平均值 \(\bar x = \frac{\sum_{i=1}^n x_i}{n}\) , \(x_i\) 为第 \(i\) 块矩形棋盘的分。
请编程对给出的棋盘及 \(n\) ，求出 \(\sigma\) 的最小值。
正文：
本题可以考虑先求出方差，在求出答案后输出其开根的结果，这样比较好算。
然后考虑二位区间 DP，其实思路很好想，用记忆化搜索做。
代码：
const int N = 20;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n;
int a[N][N];
long double f[N][N][N][N][N], barx;
long double Sum(int x1, int y1, int x2, int y2)
{
long double x = a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1] - barx;
return x * x / n;
}
long double DFS(int x1, int y1, int x2, int y2, int k)
{
if (f[x1][y1][x2][y2][k] >= 0) return f[x1][y1][x2][y2][k];
if (k == 1) return f[x1][y1][x2][y2][k] = Sum(x1, y1, x2, y2);
f[x1][y1][x2][y2][k] = 1e9;
for (int i = x1; i < x2; i++)
f[x1][y1][x2][y2][k] = min(f[x1][y1][x2][y2][k], DFS(x1, y1, i, y2, k - 1) + Sum(i + 1, y1, x2, y2)),
f[x1][y1][x2][y2][k] = min(f[x1][y1][x2][y2][k], DFS(i + 1, y1, x2, y2, k - 1) + Sum(x1, y1, i, y2));
for (int i = y1; i < y2; i++)
f[x1][y1][x2][y2][k] = min(f[x1][y1][x2][y2][k], DFS(x1, y1, x2, i, k - 1) + Sum(x1, i + 1, x2, y2)),
f[x1][y1][x2][y2][k] = min(f[x1][y1][x2][y2][k], DFS(x1, i + 1, x2, y2, k - 1) + Sum(x1, y1, x2, i));
return f[x1][y1][x2][y2][k];
}
int main()
{
n = Read();
for (int i = 1; i <= 8; i++)
for (int j = 1; j <= 8; j++)
a[i][j] = Read(),
a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
barx = a[8][8] * 1.0 / n;
memset (f, -1, sizeof f);
double ans = DFS(1, 1, 8, 8, n);
ans = sqrt(ans);
printf ("%.3f\n", ans);
return 0;
}