题目大意：给一个棋盘，棋盘上每个格子中都有一个值，现在需要将棋盘切成n个矩形，总共切n-1刀，求最小的均方差。均方差定义为：，其中
。
题目分析：将均方差化简得到：均方差2=(Σxi2)/n-平均值2。显然，平均值2是定值，为数字总和除以n。只需让矩形的和的平方和最小即可。先预处理出数组s(x1,y1,x2,y2)，表示左上角为(x1,y1)，右下角为(x2,y2)的矩形上数字和的平方，定义dp(k,x1,y1,x2,y2)表示将矩形(x1,y1,x2,y2)切k刀能获得k+1个矩形时各矩形上数字和的最小平方和。则状态转移方程为：dp(k,x1,y1,x2,y2)=min{ min(dp(k-1,x1,y1,i,y2)+s(i+1,y1,x2,y2)),min(dp(k-1,i+1,y1,x2,y2)+s(x1,y1,i,y2))), x1≤i<x2 (横着切)
min(dp(k-1,x1,y1,x2,j)+s(x1,j+1,x2,y2)),min(dp(k-1,x1,j+1,x2,y2)+s(x1,y1,x2,j))), y1≤j<y2 (竖着切)
}
代码如下：
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std; const int INF=1<<30; int w[8][8],n;
int dp[16][8][8][8][8],s[8][8][8][8]; int getS(int a,int b,int c,int d)
{
int sum=0;
for(int i=a;i<=c;++i)
for(int j=b;j<=d;++j)
sum+=w[i][j];
return sum*sum;
} void work(int x,int y)
{
for(int i=x;i<8;++i)
for(int j=y;j<8;++j)
s[x][y][i][j]=getS(x,y,i,j);
} void init()
{
for(int i=0;i<8;++i)
for(int j=0;j<8;++j)
work(i,j);
} void ceShi()
{
for(int i=0;i<8;++i)
for(int j=0;j<8;++j)
for(int k=i;k<8;++k)
for(int l=j;l<8;++l)
cout<<i<<' '<<j<<' '<<k<<' '<<l<<' '<<s[i][j][k][l]<<endl;
} int dfs(int k,int xa,int ya,int xb,int yb)
{
if(dp[k][xa][ya][xb][yb]>=0) return dp[k][xa][ya][xb][yb];
int &u=dp[k][xa][ya][xb][yb];
if(k==0) return u=s[xa][ya][xb][yb];
if(xa==xb&&ya==yb) return u=s[xa][ya][xb][yb];
u=INF;
for(int i=xa;i<xb;++i){
u=min(dfs(k-1,xa,ya,i,yb)+s[i+1][ya][xb][yb],u);
u=min(dfs(k-1,i+1,ya,xb,yb)+s[xa][ya][i][yb],u);
}
for(int i=ya;i<yb;++i){
u=min(dfs(k-1,xa,ya,xb,i)+s[xa][i+1][xb][yb],u);
u=min(dfs(k-1,xa,i+1,xb,yb)+s[xa][ya][xb][i],u);
}
return u;
} int main()
{
while(~scanf("%d",&n))
{
double sum=0.0;
for(int i=0;i<8;++i)
for(int j=0;j<8;++j){
scanf("%d",&w[i][j]);
sum+=(double)w[i][j];
}
sum/=(double)n;
memset(s,0,sizeof(s));
init();
//ceShi();
memset(dp,-1,sizeof(dp));
dfs(n-1,0,0,7,7);
double ans=(double)dp[n-1][0][0][7][7]/(double)n-sum*sum;
printf("%.3lf\n",sqrt(ans));
}
return 0;
}