Description
将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差，其中平均值，xi为第i块矩形棋盘的总分。 请编程对给出的棋盘及n，求出O’的最小值。Input 第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。Output 仅一个数，为O’（四舍五入精确到小数点后三位）。
记忆化搜索。
注意到平均数x_ bar，n这些均为常数，所以只需要最小化(xi-x_bar)^2之和。
dp[m][x1][y1][x2][y2]表示a[x1..x2][y1..y2]这块区域切成m份的最小(xi-x_bar)^2之和。
枚举切下来的那一块即可。
状态转移方程见代码。
#include<cstdio>
#include<cstring>
#include<cmath>
const int oo=0x3f3f3f3f;
const int size=8;
double x_bar,dp[17][10][10][10][10];
int n,s[10][10],a[10][10];
double min(double a,double b)
{return a<b?a:b;
}
int sum(int x1,int y1,int x2,int y2)
{return s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
}
double dfs(int m,int x1,int y1,int x2,int y2)
{if (dp[m][x1][y1][x2][y2]>=0)return dp[m][x1][y1][x2][y2];if (m==1) return (x_bar-sum(x1,y1,x2,y2))*(x_bar-sum(x1,y1,x2,y2));if (x1==x2&&y1==y2) return oo;int i,j,k,x,y,z;double ans=oo;for (i=x1;i<x2;i++){ans=min(ans,dfs(1,x1,y1,i,y2)+dfs(m-1,i+1,y1,x2,y2));ans=min(ans,dfs(m-1,x1,y1,i,y2)+dfs(1,i+1,y1,x2,y2));}for (i=y1;i<y2;i++){ans=min(ans,dfs(1,x1,y1,x2,i)+dfs(m-1,x1,i+1,x2,y2));ans=min(ans,dfs(m-1,x1,y1,x2,i)+dfs(1,x1,i+1,x2,y2));}return dp[m][x1][y1][x2][y2]=ans;
}
int main()
{int i,j,k,x,y,z;scanf("%d",&n);memset(dp,0xff,sizeof(dp));for (i=1;i<=size;i++)for (j=1;j<=size;j++){scanf("%d",&a[i][j]);s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];}x_bar=(double)s[size][size]/n;printf("%.3f\n",sqrt(dfs(n,1,1,size,size)/n));
}