P5752 [NOI1999] 棋盘分割

P5752 [NOI1999] 棋盘分割

基本同另一道棋盘分割。不同的是那道题求平方和，这道题求均方差。
$$\begin{array}{rl}\sigma & =\sqrt{\frac{\sum _{i=1}^n(x_i-\overline{x}{)}^2}{n}}\\ & =\sqrt{\frac{\sum _{i=1}^n{x}_i^2-2x_i\overline{x}+{\overline{x}}^2}{n}}\\ & =\sqrt{\frac{\sum _{i=1}^n{x}_i^2-\sum _{i=1}^{n}2x_i\overline{x}+\sum _{i=1}^n{\overline{x}}^2}{n}}\\ & =\sqrt{\frac{\sum _{i=1}^n{x}_i^2-2\overline{x}\sum _{i=1}^n{x}_i+n{\overline{x}}^2}{n}}\end{array}$$
其中
$$\begin{array}{rl}& \frac{\sum _{i=1}^n{x}_i}{n}=\overline{x}\\ ⟹& \sum _{i=1}^n{x}_i=n\overline{x}\end{array}$$

带入上式
$$\begin{array}{rl}\sigma & =\sqrt{\frac{\sum _{i=1}^n{x}_i^2-2\overline{x}\sum _{i=1}^n{x}_i+n{\overline{x}}^2}{n}}\\ & =\sqrt{\frac{\sum _{i=1}^n{x}_i^2-2\overline{x}n\overline{x}+n{\overline{x}}^2}{n}}\\ & =\sqrt{\frac{\sum _{i=1}^n{x}_i^2-n{\overline{x}}^2}{n}}\end{array}$$
而此题中，总和和分割的个数都已知，所以平均数是确定，答案最小时，也就是平方和最小。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int inf = 1e9;
int n, v[9][9], s[9][9], f[9][9][9][9][16];
int sum(int x1, int y1, int x2, int y2)
{
    int t = s[x2][y2] + s[x1 - 1][y1 - 1] - s[x2][y1 - 1] - s[x1 - 1][y2];
    return t * t;
}
int dfs(int x1, int y1, int x2, int y2, int t)
{
    if (~f[x1][y1][x2][y2][t])
        return f[x1][y1][x2][y2][t];
    if (!t)
        return sum(x1, y1, x2, y2);
    int res = inf;
    for (int i = x1 + 1; i <= x2; i++)
        res = min(res, sum(x1, y1, i - 1, y2) + dfs(i, y1, x2, y2, t - 1));
    for (int i = x2 - 1; i >= x1; i--)
        res = min(res, sum(i + 1, y1, x2, y2) + dfs(x1, y1, i, y2, t - 1));
    for (int i = y1 + 1; i <= y2; i++)
        res = min(res, sum(x1, y1, x2, i - 1) + dfs(x1, i, x2, y2, t - 1));
    for (int i = y2 - 1; i >= y1; i--)
        res = min(res, sum(x1, i + 1, x2, y2) + dfs(x1, y1, x2, i, t - 1));
    f[x1][y1][x2][y2][t] = res;
    return res;
}
int main()
{
    memset(f, -1, sizeof f);
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++)
        {
            cin >> v[i][j];
            sum += v[i][j];
        }
    for (int i = 1; i <= 8; i++)
        for (int j = 1; j <= 8; j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v[i][j];
    int t = dfs(1, 1, 8, 8, n - 1);

    printf("%.3f", sqrt((double)t / n - ((double)sum * sum / n / n)));
    return 0;
}