poj 1191 棋盘分割(dp + 记忆化搜索)

题目：http://poj.org/problem?id=1191

黑书116页的例题

将方差公式化简之后就是 每一块和的平方 相加/n , 减去平均值的平方。

可以看出来 方差只与 每一块的和的平方有关，所以就是求每个矩形的总分的平方和 尽量小。。。。

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 using namespace std;

 const int INF = <<;

 int sum[][], d[][][][][];//sum存储从【1,1】到【i, j】的和

 int _min(int a, int b)

 {

     return a>b?b:a;

 }

 int getsum(int x1, int y1, int x2, int y2) //计算从【x1,y1】到【x2, y2】的和。

 {

     return sum[x2][y2]-sum[x1-][y2]-sum[x2][y1-]+sum[x1-][y1-];

 }

 int slove(int k, int x1, int y1, int x2, int y2)

 {

     int s1, s2, Min, temp1, temp2;

     int i;

     if(d[k][x1][y1][x2][y2]!=-) //不等于1表示已经求过了，不需要再求了

     return d[k][x1][y1][x2][y2];

     if(k == )  //表示已经切了n块了，不需要再切了

     {

         s1 = getsum(x1, y1, x2, y2);

         return (d[k][x1][y1][x2][y2] = s1*s1);

     }

     Min = INF;

     for(i = x1; i < x2; i++)  //横向切

     {

         s1 = getsum(x1, y1, i, y2);

         s2 = getsum(i+, y1, x2, y2);

         temp1 = _min(slove(k-, i+, y1, x2, y2)+s1*s1, slove(k-, x1, y1, i, y2)+s2*s2);

         if(temp1 < Min)

         Min = temp1;

     }

     for(i = y1; i < y2; i++) //纵向切

     {

         s1 = getsum(x1, y1, x2, i);

         s2 = getsum(x1, i+, x2, y2);

         temp2 = _min(slove(k-, x1, i+, x2, y2)+s1*s1, slove(k-, x1, y1, x2, i)+s2*s2);

         if(temp2 < Min)

         Min = temp2;

     }

     return (d[k][x1][y1][x2][y2] = Min);

 }

 int main()

 {

     int n, i, j, val, x;

     double aver, var;

     while(~scanf("%d", &n))

     {

         memset(d, -, sizeof(d));

         memset(sum, , sizeof(sum));

         for(i = ; i <= ; i++)

         for(j = , x = ; j <= ; j++)

         {

             scanf("%d", &val);

             x += val;

             sum[i][j] = sum[i-][j] + x;

         }

         aver = sum[][]*1.0/n;  //所有块的平方和

         int sum_t = slove(n, , , , );

         var = sqrt(sum_t*1.0/n-aver*aver);

         printf("%.3lf\n", var);

     }

     return ;

 }