321 棋盘分割（高维区间dp）

蔚落 2022-09-13 04:26 134阅读 0赞

**1. 问题描述：**

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

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_13_color_FFFFFF_t_70_g_se_x_16][]  
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成 n 块矩形棋盘，并使各矩形棋盘总分的均方差最小。均方差和平均值的公式如下图所示，其中xi为第i块矩形棋盘的的总分，请编程对给出的棋盘及 n，求出均方差的最小值。

![20210927174521818.png][]

![20210927174329443.png][]

**输入格式**

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

**输出格式**

输出最小均方差值（四舍五入精确到小数点后三位）。

**数据范围**

1 < n < 15

**输入样例：**

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

**输出样例：**

1.633  
来源：[https://www.acwing.com/problem/content/description/323/][https_www.acwing.com_problem_content_description_323]

**2. 思路分析：**

分析题目可以知道每一次切割的时候都是对某一个剩余的矩形切一刀，这样就可以将当前的矩形分为两个子矩形，然后对其中一个矩形再进行同样的操作（另外一个矩形不能再切了），我们需要在所有可能的切割方案中找到均方差最小的切割方案，所以这道题目属于最优化问题，可以使用搜索或者动态规划解决，下面使用动态规划的思想来分析，dfs搜索来实现的方法（由于涉及到高维数组在状态计算的时候需要使用很多层的循环所以使用dfs搜索比较方便，dfs方法中传递相关的参数搜索即可），动态规划可以看成是对暴力枚举的优化，数组中的某一个值其实表示的是一类方案的集合所以可以到达优化的目的。动态规划一般分为两个步骤：① 状态表示； ② 状态计算；因为是在一个矩阵中进行切割操作，所以涉及到矩阵左上角与右下角的坐标，并且一个矩阵可以切割为k部分，所以需要使用五维来表示，也即需要声明一个五维数组来表示，其中dp\[x1\]\[y1\]\[x2\]\[y2\]\[k\]表示将当前的矩阵（x1，y1）(x2，y2)切割为k部分的所有方案中均方差的最小值；怎么样进行状态计算呢？状态计算对应集合的划分，一般是找最后一个不同点，对于当前的dp\[x1\]\[y1\]\[x2\]\[y2\]\[k\]代表的集合，我们可以切一刀，分为横着切与竖着切的两部分，其实对于这两部分内部又分为保留上半部分还是下半部分分为两个集合，保留的部分值是可以直接计算出结果的，需要切割的部分又可以执行相同的过程，所以可以发现切割的过程是一个递归的过程，使用递归解决即可，我们可以借助于声明的五维数组记录之前已经求解过的值，当发现之前已经求解过了那么就可以直接返回了，主要是理解其中的划分方式。对于每一个矩阵切一刀之后分成的两部分是相互独立的所以可以看成是**高维的区间dp问题，**每一部分求解最小值相加就是整个部分的最小值。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

**python代码：**

from typing import List
    import math
    
    class Solutuon:
        # 声明一个全局的列表dp这样就不用在递归方法中传递这么多维的参数
        dp = None
        # X为平均数
        X, n = 0, 0
        
        def getSum(self, x1: int, y1: int, x2: int, y2: int, s: List[List[int]]):
            return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
        
        # 计算(x1, y2), (x2, y2)构成的子矩阵对应的公式值, 也即(xi - _x) ^ 2
        def get(self, x1: int, y1: int, x2: int, y2: int, s: List[List[int]]):
            sum = self.getSum(x1, y1, x2, y2, s) - self.X
            return sum * sum / self.n
        
        # 递归求解保留的部分与需要往下递归的部分
        def dfs(self, x1: int, y1: int, x2: int, y2: int, k: int, s: List[List[int]]):
            if self.dp[x1][y1][x2][y2][k] >= 0: return self.dp[x1][y1][x2][y2][k]
            if k == 1: return self.get(x1, y1, x2, y2, s)
            v = 10 ** 9
            # 横着切, 使用循环的目的尝试当前矩阵切的各个位置
            for i in range(x1, x2):
                # 保留上半部分 + 递归下半部分
                v = min(v, self.get(x1, y1, i, y2, s) + self.dfs(i + 1, y1, x2, y2, k - 1, s))
                # 保留下半部分 + 递归上半部分
                v = min(v, self.get(i + 1, y1, x2, y2, s) + self.dfs(x1, y1, i, y2, k - 1, s))
            # 竖着切
            for i in range(y1, y2):
                # 保留上半部分 + 递归下半部分
                v = min(v, self.get(x1, y1, x2, i, s) + self.dfs(x1, i + 1, x2, y2, k - 1, s))
                # 保留下半部分 + 递归上半部分
                v = min(v, self.get(x1, i + 1, x2, y2, s) + self.dfs(x1, y1, x2, i, k - 1, s))
            # 记忆化的过程
            self.dp[x1][y1][x2][y2][k] = v
            return v
    
        def process(self):
            N = 9
            n = int(input())
            self.n = n
            # a存储每一个格子的评分
            a = list()
            for i in range(8):
                a.append(list(map(int, input().split())))
            # 二维前缀和预处理, 下标从1开始计算, 其实画图会比较容易写出具体的公式
            s = [[0] * (N + 1) for i in range(N + 1)]
            for i in range(1, N):
                for j in range(1, N):
                    s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i - 1][j - 1]
            self.X = s[8][8] / n
            # 需要声明五维列表, dp为五维列表, -1表示不合法
            self.dp = [[[[[-1] * (n + 1) for i in range(N)] for j in range(N)] for k in range(N)] for l in range(N)]
            res = self.dfs(1, 1, 8, 8, n, s)
            # 保留三位小数输出
            return "{:.3f}".format(math.sqrt(res))
    
    
    if __name__ == '__main__':
        print(Solutuon().process())

**c++代码：**

#include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    const int N = 15, M = 9;
    const double INF = 1e9;
    
    int n, m = 8;
    int s[M][M];
    double f[M][M][M][M][N];
    double X;
    
    int get_sum(int x1, int y1, int x2, int y2)
    {
        return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
    }
    
    double get(int x1, int y1, int x2, int y2)
    {
        double sum = get_sum(x1, y1, x2, y2) - X;
        return (double)sum * sum / n;
    }
    
    double dp(int x1, int y1, int x2, int y2, int k)
    {
        double &v = f[x1][y1][x2][y2][k];
        if (v >= 0) {
            return v;
        }
        if (k == 1) return v = get(x1, y1, x2, y2);
    
        v = INF;
        for (int i = x1; i < x2; i ++ )
        {
            v = min(v, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));
            v = min(v, get(i + 1, y1, x2, y2) + dp(x1, y1, i, y2, k - 1));
        }
        for (int i = y1; i < y2; i ++ )
        {
            v = min(v, get(x1, y1, x2, i) + dp(x1, i + 1, x2, y2, k - 1));
            v = min(v, get(x1, i + 1, x2, y2) + dp(x1, y1, x2, i, k - 1));
        }
         f[x1][y1][x2][y2][k] = v;
        return v;
    }
    
    int main()
    {
        cin >> n;
        for (int i = 1; i <= m; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                cin >> s[i][j];
                s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
            }
    
        X = (double)s[m][m] / n;
        memset(f, -1, sizeof f);
        printf("%.3lf\n", sqrt(dp(1, 1, 8, 8, n)));
        return 0;
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1ba81915f0a340e491dbafe50f802c25.png
[20210927174521818.png]: /images/20220828/b365b26938d4429787d248f36dd54608.png
[20210927174329443.png]: /images/20220828/c270a2b4f5e8421bb2b0f6f208347c86.png
[https_www.acwing.com_problem_content_description_323]: https://www.acwing.com/problem/content/description/323/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e4234896492141bb9965d1ca01e4aa9a.png