COGS 100. [NOI1999] 棋盘分割

★★   输入文件：division.in   输出文件：division.out   简单对比

时间限制：1 s   内存限制：128 MB

【问题描述】

  将一个８×８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将分割过的部分任选一块继续如此分割，这样割了n-1次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)

    原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n 块矩形棋盘，并使各矩形棋盘总分的均方差最小。

均方差

 ，其中平均值

 x i 为第 i 块矩形棋盘的分。

请编程对给出的棋盘及 n ，求出 

的最小值。

 

【输入格式】

第 1 行为一个整数 n(1<n<9) 。<="" div="">

第 2 行至第 9 行每行为 8 个小于 100 的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。

【输出格式】

   

仅一个数，为 

（四舍五入精确到小数点后三位）。

【输入样例】

输入文件名：division.in

3 

1 1 1 1 1 1 1 3 

1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 1 

1 1 1 1 1 1 1 0 

1 1 1 1 1 1 0 3

输出文件名：division.out

1.633

注意合法的切割方案是指 切了一刀后，选其中一块继续切，另一块不能再切

首先将均方差公式变形

 

第三个等号到第四个等号的变换：

 

平均值固定不变，所以只需最小化每个矩形总分的平方和

dp[k][x1][x2][y1][y2] 矩形左上角标号为（x1，y2） ，右上角标号为（x2，y2），分为k个矩形 所得到的最小平方和

初始化：dp 极大值

预处理：s[x1][x2][y1][y2]   矩形左上角标号为（x1，y2） ，右上角标号为（x2，y2）内所有数和的平方

          dp[1][x1][x2][y1][y2]=s[x1][x2][y1][y2] （相当于一刀也不切的情况）

状态转移：dp[k][x1][y1][x2][y2]=min(

             dp[k-1][x1][y1][x][y2]+s[x+1][y1][x2][y2]) //横着切，取上面一部分继续切

             dp[k-1][x+1][y1][x2][y2]+s[x1][y1][x][y2]//横着切，取下面一部分继续切

             dp[k-1][x1][y1][x2][y]+s[x1][y+1][x2][y2]//竖着切，取左边一部分继续切 

             dp[k-1][x1][y+1][x2][y2]+s[x1][y1][x2][y] //竖着切，取右边一部分继续切

)

转移过程可用记忆化搜索实现

 

#include
       
        #include
        
         #include
         
          #include
          
           #define INF 1e9using namespace std;int n,a[9][9],dp[16][9][9][9][9],s[9][9][9][9];int add(int x1,int y1,int x2,int y2){    int tmp=0;    for(int i=x1;i<=x2;i++)     for(int j=y1;j<=y2;j++)      tmp+=a[i][j];    return tmp;}int dfs(int k,int x1,int y1,int x2,int y2){    if(dp[k][x1][y1][x2][y2]!=INF) return dp[k][x1][y1][x2][y2];    if(x2>x1)    {        for(int i=x1;i
           
            y1)    {        for(int i=y1;i