根据这2个公式可以 得到 O^2 = sum(x1^2 + x2^2 + x3^2 +...xi^2)/n - 平均值^2
所以我们就是要使得总分的平方和尽量小……
对于一次切割，可以横着切，可以竖着切，可以使剩下了的包含左上角，也可以使剩下了的包含右上角。
具体方程什么的看代码吧。
G++提交的时候记得把.3lf改成.3f
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
double sum[9][9];
double a[9][9];
int n;
double ave;
double d[16][9][9][9][9];
double s(int x1,int y1,int x2,int y2)
{
double tmp=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
return tmp*tmp;
}
double dfs(int k,int x1,int y1,int x2,int y2)
{
if(k==1)
{
d[k][x1][y1][x2][y2]=s(x1,y1,x2,y2);
return d[k][x1][y1][x2][y2];
}
if(d[k][x1][y1][x2][y2]) return d[k][x1][y1][x2][y2];
double t1=100000000,t2=100000000;
for(int a=x1;a<x2;a++)
{
t1=min(t1,min(dfs(k-1,x1,y1,a,y2)+s(a+1,y1,x2,y2),dfs(k-1,a+1,y1,x2,y2)+s(x1,y1,a,y2)));
}
for(int b=y1;b<y2;b++)
{
t2=min(t2,min(dfs(k-1,x1,y1,x2,b)+s(x1,b+1,x2,y2),dfs(k-1,x1,b+1,x2,y2)+s(x1,y1,x2,b)));
}
d[k][x1][y1][x2][y2]=min(t1,t2);
return d[k][x1][y1][x2][y2];
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(sum,0,sizeof(sum));
memset(d,0,sizeof(d));
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
{
scanf("%lf",&a[i][j]);
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
ave=sum[8][8]/n;
dfs(n,1,1,8,8);
printf("%.3f\n",sqrt(d[n][1][1][8][8]/n-ave*ave));
}
return 0;
}