题意：n刀切割棋盘

下面是8*8的棋盘，每个数字代表棋盘对应点的权值，问切割n刀后，每一块的和 的均方差最小是多少

均方差的公式需要先化简：

由上式得，均方差最小 显然是要 Xi^2 最小

d[k][x1][y1][x2][y2]代表棋盘从(x1,y1)->(x2,y2)已经切了k刀 获得的最小的平方和

用sum[i][j] 代表 从(1,1)点 到 (i,j)点的权值和

这样答案就是 dp[n][1][1][8][8]/n -(sum[8][8]/n)^2

用S[ (x1,y1) ,( x2,y2) ] 代表 这两点间的权值和

这里用递归dp

状态转移方程：

d[k][x1][y1][x2][y2]=

Min{ 横向切： d[k-1] +剩下未切部分的平方和，纵向切：d[k-1]+剩下未切部分的平方和 }

横向切的最优解就是 Min{ d[ k-1,(x1,y1) , ( i ,y2) ] + S[ (i +1,y1) , ( x2 ,y2) ] , d[ k-1,(i+1,y1) , ( x2 ,y2) ] + S[ (x1,y1) , ( i ,y2) ] } ( x1<= i

上面的意思就是： 在x=i处切一刀的最优解

同理可以容易推出纵向切法的dp方程

#include
#include
#include 
#define INF 1<<29
int map[9][9],sum[9][9];
int d[15][9][9][9][9];
inline int Min(int a,int b){return a>b b:a;}

int s(int x1,int y1,int x2,int y2){
	int temp=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]; return temp*temp;
}

int dp(int k,int x1,int y1,int x2,int y2){
	if(d[k][x1][y1][x2][y2]!=-1)return d[k][x1][y1][x2][y2];
	if(k==1)return s(x1,y1,x2,y2);
	int ans=INF,i;
	for(i=x1;i