1>根据公式化简：

其中后者是一个已知数。求均方差的最小值就是求出个个棋盘内各数值的平方和最小值。

2>棋盘分割分四种情况：

竖切（左不动），竖切（右不动），横切（上不动），横切（下不动）；

3>状态转移方程：

f(i, x1, y1, x2, y2)表示以（x1, y1),(x2, y2)为四边形对角线的棋盘切割成i块的各块值总平方的最小值；

D(x1, y1, x2, y2)表示棋盘的总分

 

                   _____________ 

                   | f(i-1, x1, a+1, x2, y2)+D(x1, y1, x2, a)   [横切（上不动）]

                   | f(i-1, x1,y1, x2, a)+D(x1, a+1, x2, y2)   [横切（下不动）] 

f(i, x1, y1, x2, y2)=min| f(i-1,b+1, y1, x2, y2)+D(x1, y1, b1, y2)  [竖切（左不动）]

                   | f(i-1, x1, y1, b, y2)+D(b+1, y1, x2, y2)   [竖切（右不动）]

                   ______________

4>其中的a, b是进行枚举的值。先预处理D（x1, y1, x2, y2)

代码如下：

/***  POJ 1191 棋盘分割*/#include
      
       #include
       
        #include
        
         int a[9][9], F[15][9][9][9][9];int minx(int a1, int a2, int a3){    int minnum=99999999;    if(a1