棋盘分割

小K算法

发布于 2022-11-24 08:02:50

64300

代码可运行

文章被收录于专栏：小K算法小K算法

运行总次数：0

代码可运行

作者 | 小K

出品 | 公众号：小K算法

故事起源

有一个8*8的棋盘，沿着格子的边进行分割，每分割一块拿走，将剩下的矩形棋盘继续分割。

n-1次分割后，可以得到n块矩形棋盘。

假设原棋盘每一格都有一个分值，则分割后的每一块都有一个总分，总分即为所有格子分值之和。

设分割的每一块棋盘总分为xi。

如何分割可以让各矩形棋盘总分的均方差最小？

分析

先对均方差公式作一些简化。

通过上面公式可以看出，其实就是要求分割后的n个矩形棋盘，分值平方的总和最小。

当你遇到一些没有头绪的问题的时候，先不要想太多，别上来整什么高大上的思想，咱们就从最简单的场景开始分析。

2.1

缩小问题规模

假设棋盘规模不是8*8，而是2*2。缩小问题规模是一种很有用的方法，因为问题的本质并没有发生变化，只是数据更小，就更有利于我们分析问题的本质。

2.2

开始分割

这时再让你分割，还会觉得难吗，全部手动枚举也能解决啊。

先垂直切。

先水平切。

切2次，分割成3块，总共也就4种情况，把每一种情况的方差算出来，选一个最小的就行了。

2.3

规律

每次分割有2种决策，要么水平切，要么垂直切。

针对一种决策，又有很多种具体的不同的切法。例如一个4*4的棋盘，先垂直切，就可以从3个不同的位置切。

如果给棋盘加一个坐标，每一种切法就可以用一个线段来具体表示，比如用这条切线的两个端点坐标。

分割之后，就变成了2个更小的棋盘，而这2个棋盘也可以用矩形的坐标表示，此时就把原问题变成了子问题，原问题的最优解也就是所有子问题中选一个最优的。

此时你可能会有几个疑问：

1.为什么全局最优解可以转化为子问题的最优解呢？上面的分割方法，在每一个阶段，我们已经把所有可能的分割方法全部枚举完了，那其中的最优肯定就是当前阶段的最优了，因为没有其它的可能性。

2.为什么当前阶段的最优可以转化为下一阶段？这就是一个无后效性，因为我们只需要分割的分值平方和最小，并不关心它具体是怎么分割的。之前怎么分割，在当前阶段看来都是一样的，不受影响。

3.应该用几维来表示状态呢？这个就是到底要开几维数组来递推。上面无论是表示分割的线段，还是分割后的矩形，都至少要2个点坐标，所以至少得4维。

建模

先垂直切，继续切左边或者右边，找出最优解。

先水平切，继续切上边或者下边，找出最优解。

当前轮次t只与上一次t-1有关，所以可以用01滚动数组，压缩一维。

初始化的时候，所有小块的独立矩形棋盘都一次不切，所以就是矩形棋盘的分值平方。

代码实现

定义

#define N 9
int chessboard[N][N];
int d[2][N][N][N][N];
int sum[N][N] = {0};

int getSum(int x, int y, int k, int l) {
    int ans = sum[k][l] - sum[k][y - 1] - sum[x - 1][l] + sum[x - 1][y - 1];
    return ans * ans;
}

int min(int x, int y) {
    return x < y ? x : y;
}

初始化

void init() {
  for (int i = 1; i <= 8; ++i) {
        for (int j = 1; j <= 8; ++j) {
            cin >> chessboard[i][j];
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + chessboard[i][j];
        }
    }
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j < N; ++j) {
            for (int k = i; k < N; ++k) {
                for (int l = j; l < N; ++l) {
                    d[0][i][j][k][l] = getSum(i, j, k, l);
                }
            }
        }
    }
}

main

int main() {
    int n;
    cin >> n;
    init();
    int s = 0;
    for (int t = 1; t < n; ++t) {
        s = 1 - s;
        // 枚举起点
        for (int i = 1; i < N; ++i) {
            for (int j = 1; j < N; ++j) {
                // 枚举终点
                for (int k = i; k < N; ++k) {
                    for (int l = j; l < N; ++l) {
                        d[s][i][j][k][l] = 1e8;
                        // 横切
                        for (int a = i; a < k; ++a) {
                            d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][j][a][l] + getSum(a + 1, j, k, l));
                            d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][a + 1][j][k][l] + getSum(i, j, a, l));
                        }
                        // 纵切
                        for (int b = j; b < l; ++b) {
                            d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][j][k][b] + getSum(i, b + 1, k, l));
                            d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][b + 1][k][l] + getSum(i, j, k, b));
                        }
                    }
                }
            }
        }
    }
    double average = sum[N - 1][N - 1] * 1.0 / n;
    double ans = d[s][1][1][8][8] * 1.0 / n - average * average;
    printf("%.3lf", sqrt(ans));
    return 0;
}