P5752 [NOI1999] 棋盘分割

P5752 [NOI1999] 棋盘分割

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

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

查看代码

#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;
}