题目传送门：Link

这个题目很重要的条件就是：

每次切割都只能沿着棋盘格子的边进行。

关于这个条件的解释，题面中已经写的很清楚了，我就不赘述了。

考虑使均方差 $\sigma=\sqrt{\dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2}{n}}$ 最小

则考虑使标准差 $\alpha=\dfrac{\sum\limits_{i=1}^{n}(x_i-\bar{x})^2}{n}$ 最小

分析得到 $\bar{x}=\dfrac{\sum\limits_{i=1}^nx_i}{n}$ 无论 $x_i$ 的取值 ，$\bar{x}$ 恒等于 $\dfrac{\sum\limits_{i=1}^8\sum\limits_{j=1}^8w_{i,j}}{n}$，其中 $w_{i,j}$ 代表每一个格子上的数。

所以可以预处理 $\bar{x}$。

此时可以发现将每个 $x_i$ 分开考虑，使得 $\dfrac{(x_i-\bar{x})^2}{n}$ 最小，即考虑使用动态规划。

由于此题是一个比较明显的区间分割问题，考虑使用区间 DP。

令 $f_{x_1,y_1,x_2,y_2,k}$ 表示将子矩阵 $(x_1,y_1)(x_2,y_2)$ 划分为 $k$ 个子矩阵的最小标准差 $\alpha$，则最终答案为 $\sqrt{f_{1,1,8,8,n}}$。

边界 $k=1$ 时，$f_{x_1,y_1,x_2,y_2,k}=\dfrac{((\sum\limits_{i=x_1}^{x_2}\sum\limits_{j=y_1}^{y_2}w_{i,j})-\bar{x})^2}{n}$

在状态转移时，分类讨论水平切还是竖直切，枚举在哪里切，再分类讨论是要哪一块。

则可得出状态转移方程（详见代码）。

注意可用二维前缀和来维护子矩阵，从而 $O(1)$ 得到子矩阵的和。

总时间复杂度 $O(8^5n)$。

由于循环太多，采用记忆化搜索写。

代码中 X 即为 $\bar{x}$，get 函数是求 $\dfrac{(x_i-\bar{x})^2}{n}$，s 即为二位前缀和数组。

注意 X 计算时别忘了强制转换 s 数组的

#include<bits/stdc++.h>
using namespace std;
double f[9][9][9][9][15];
int s[9][9];
double X;
int n;
double get(int x_1,int y_1,int x_2,int y_2)
{
    double sum=s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1]-X;
    return sum*sum/n;
}
double dp(int x_1,int y_1,int x_2,int y_2,int k)
{
    if(f[x_1][y_1][x_2][y_2][k]>=0) return f[x_1][y_1][x_2][y_2][k];
    if(k==1) return f[x_1][y_1][x_2][y_2][k]=get(x_1,y_1,x_2,y_2);
    f[x_1][y_1][x_2][y_2][k]=1e9;
    for(int i=x_1;i<x_2;i++)
    {
        f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],dp(x_1,y_1,i,y_2,k-1)+get(i+1,y_1,x_2,y_2));
        f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],dp(i+1,y_1,x_2,y_2,k-1)+get(x_1,y_1,i,y_2));
    }
    for(int i=y_1;i<y_2;i++)
    {
        f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],dp(x_1,y_1,x_2,i,k-1)+get(x_1,i+1,x_2,y_2));
        f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],dp(x_1,i+1,x_2,y_2,k-1)+get(x_1,y_1,x_2,i));
    }
    return f[x_1][y_1][x_2][y_2][k];
}
int main()
{
    cin>>n;
    for(int i=1;i<=8;i++)
    {
        for(int j=1;j<=8;j++)
        {
            scanf("%lf",&s[i][j]);
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    memset(f,-1,sizeof f);
    X=(double)s[8][8]/n;
    printf("%.3lf\n",sqrt(dp(1,1,8,8,n)));
}

这个 memset 是一个很玄学的东西，害的我调了半天。

于是我还是写了一份循环的

#include<bits/stdc++.h>
using namespace std;
double f[9][9][9][9][15];
int s[9][9];
double X;
int n;
inline double get(int x_1,int y_1,int x_2,int y_2)
{
    double sum=s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1]-X;
    return sum*sum/n;
}
int main()
{
    cin>>n;
    for(int i=1;i<=8;i++)
    {
        for(int j=1;j<=8;j++)
        {
            cin>>s[i][j];
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
    }
    X=(double)s[8][8]/n;
    for(int k=1;k<=n;k++)
    {
        for(int x_1=1;x_1<=8;x_1++)
        {
            for(int y_1=1;y_1<=8;y_1++)
            {
                for(int x_2=1;x_2<=8;x_2++)
                {
                    for(int y_2=1;y_2<=8;y_2++)
                    {
                        f[x_1][y_1][x_2][y_2][k]=1e9;
                        if(k==1)
                        {
                            f[x_1][y_1][x_2][y_2][k]=get(x_1,y_1,x_2,y_2);
                            continue;
                        }
                        for(int i=x_1;i<x_2;i++)
                        {
                            f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],f[x_1][y_1][i][y_2][k-1]+get(i+1,y_1,x_2,y_2));
                            f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],f[i+1][y_1][x_2][y_2][k-1]+get(x_1,y_1,i,y_2));
                        }
                        for(int i=y_1;i<y_2;i++)
                        {
                            f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],f[x_1][y_1][x_2][i][k-1]+get(x_1,i+1,x_2,y_2));
                            f[x_1][y_1][x_2][y_2][k]=min(f[x_1][y_1][x_2][y_2][k],f[x_1][i+1][x_2][y_2][k-1]+get(x_1,y_1,x_2,i));
                        }
                    }
                }
            }
        }
    }
    printf("%.3lf\n",sqrt(f[1][1][8][8][n]));
}

再次强调 $f_{x_1,y_1,x_2,y_2,k}$ 是存储的将子矩阵 $(x_1,y_1)(x_2,y_2)$ 划分为 $k$ 个子矩阵的最小标准差 $\alpha$，所以最后还要开根号！