$\sqrt{\frac{\sum (x_i-\overline{x})^2}{n}}=\sqrt{\frac{\sum ({x_i}^2-2x_i\overline{x}+ \overline{x}^2)}{n}}=\sqrt{\frac{\sum {x_i}^2}{n}-\overline{x}^2}$

知道这个后就好做了,只需处理前缀和就可以了。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[16][9][9][9][9],sum[9][9];
int main()
{
    int n;qr(n);
    for(int i=1;i<=8;i++)
        for(int j=1,x;j<=8;j++)
        {
            qr(x);sum[i][j]=sum[i-1][j]+sum[i][j-1]+x-sum[i-1][j-1];
        }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=8;i++)    
        for(int j=1;j<=8;j++)
            for(int x=1;x<=8;x++)
                for(int y=1;y<=8;y++)
                {
                    f[0][i][j][x][y]=sum[x][y]-sum[x][j-1]-sum[i-1][y]+sum[i-1][j-1];
                    f[0][i][j][x][y]*=f[0][i][j][x][y];
                }
    for(int t=1;t<n;t++)
        for(int i=1;i<=8;i++)
            for(int j=1;j<=8;j++)
                for(int x=1;x<=8;x++)
                    for(int y=1;y<=8;y++)
                    {
                        int &ms=f[t][i][j][x][y];
                        /*采取一种倒推的做法*/
                        /*切完一刀,两边都是矩形*/
                        /*每次切割棋盘只有两种选择,要么横切要么竖切,切一刀下去,会分成两个矩形,只能为两个子矩阵(一个被割了0次,一个被割了t-1次)*/
                        for(int a=i;a<x;a++)ms=min(ms,min(f[t-1][i][j][a][y]+f[0][a+1][j][x][y],f[0][i][j][a][y]+f[t-1][a+1][j][x][y]));
                        for(int b=j;b<y;b++)ms=min(ms,min(f[t-1][i][j][x][b]+f[0][i][b+1][x][y],f[0][i][j][x][b]+f[t-1][i][b+1][x][y]));                 
                    }
    printf("%.3lf\n",sqrt(1.0*f[n-1][1][1][8][8]/n-1.0*sum[8][8]*sum[8][8]/n/n));
    return 0;
}