棋盘分割——维数较大的动态规划

一、问题描述

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

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

二、解题思路 / n

σ = √∑(x_i- x) ²/ n,x = ∑xi / n

x为平均值，把不管如何切割，已经确定了。

我们把标准差公式变形（只考虑根号内）：

∑(x_i- x) ²/ n = ∑(x_i² + x²- 2*x_i*x) / n

　　　　　 =( ∑x_i²+ ∑x² - 2*x*∑x_i) / n

　　　　　 = ( ∑x_i²+ n*x² - 2*x*nx) / n

　　　　　 = ∑x_i²/ n - x²

所以求标准差的最小值，等价于求平方和的最小值。

用d[k][x1][x2][y1][y2]表示1--x2,y1--y2围成的矩形切割k次平方和的最小值

横着切：d[k - 1][x1][a][y1][y2] + sum[a + 1][x2][y1][y2]（选上边，加下边）

　　　　d[k - 1][a + 1][x2][y1][y2] + sum[x1][a][y1][y2]（选下边，加上边）

竖着切： d[k - 1][x1][x2][y1][b] + sum[x1][x2][b + 1][y2]（选右边，加左边）

　　　　 d[k - 1][x1][x2][b + 1][y2] + sum[x1][x2][y1][b]（选左边，加右边）

k作为阶段，初始化k ==0 的情况，即未切，易知d[0][x1][x2][y1][y2] = sum[x1][x2][y1][y2],k从小到大递推，d[n - 1][0][7][0][7]就是n个块平方和的最大值。

三、代码实现

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 const int INF = 0x3f3f3f3f;
 9 int n;
10 int arr[10][10];
11 int sum[10][10][10][10];        //sum[x1][x2][y1][y2]表示x1--x2,y1--y2围成矩形的面积
12 int d[20][10][10][10][10];        //d[k][x1][x2][y1][y2]表示1--x2,y1--y2围成的矩形切割k次平方和的最小值
13 
14 void init()
15 {
16     for (int x1 = 0; x1 < 8; x1++)
17         for (int x2 = x1; x2 < 8; x2++)
18             for (int y1 = 0; y1 < 8; y1++)
19                 for (int y2 = y1; y2 < 8; y2++)
20                 {
21                     int res = 0;
22                     for (int a = x1; a <= x2; a++)
23                         for (int b = y1; b <= y2; b++)
24                             res += arr[a][b];
25                     sum[x1][x2][y1][y2] = res * res;
26                 }
27 }
28 
29 void slove()
30 {
31     init();
32     for(int k = 0;k < n;k++)
33         for(int x1 = 0;x1 < 8;x1++)
34             for(int x2 = x1;x2 < 8;x2++)
35                 for(int y1 = 0;y1 < 8;y1++)
36                     for (int y2 = y1; y2 < 8; y2++)
37                     {
38                         if (k == 0)  d[k][x1][x2][y1][y2] = sum[x1][x2][y1][y2];
39                         else
40                         {
41                             int tmp1 = INF,tmp2 = INF;
42                             int& ans = d[k][x1][x2][y1][y2];
43                             ans = INF;
44                             for (int a = x1; a < x2; a++)
45                                 tmp1 = min(tmp1,min(d[k - 1][x1][a][y1][y2] + sum[a + 1][x2][y1][y2], d[k - 1][a + 1][x2][y1][y2] + sum[x1][a][y1][y2]));
46                             for (int b = y1; b < y2; b++)
47                                 tmp2 = min(tmp2,min(d[k - 1][x1][x2][y1][b] + sum[x1][x2][b + 1][y2], d[k - 1][x1][x2][b + 1][y2] + sum[x1][x2][y1][b]));
48                             ans = min(ans, min(tmp1, tmp2));
49                         }
50                     }
51 
52     double res = sqrt((double)d[n - 1][0][7][0][7] / n - (double)sum[0][7][0][7] / ((double)n * n));    //注意开根号，血的教训啊
53     printf("%.3lf
",res );
54 }
55 
56 int main()
57 {
58     while (scanf("%d",&n) == 1)
59     {
60         for (int i = 0; i < 8; i++)
61             for (int j = 0; j < 8; j++)
62                 scanf("%d", &arr[i][j]);
63         slove();
64     }
65 }

四、总结

准确的说，这还是我第一次对数学公式进行化简求解问题，可见数学归纳、再化简是解决问题的一种重要方法。

同时，这也是我第一次做三维以上的动态规划题（虽然与二维三维没多大区别，但也客服了一点心理恐惧），再次使用递推解决问题，而不是记忆化搜索，进一步加深了我对“阶段”，也就是各维循环顺序的理解。