「洛谷 P1436」棋盘分割 - 区间 DP

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

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

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

请编程对给出的棋盘及 \(n\) ，求出平方和的最小值。

数据范围：\(1 \leq n \leq 15\)

解题思路

显然这道题可以用区间 DP 来做。我们定义如下状态：

\[ f_{i, l, d, r, u} \quad i, l, d, r, u \in [1, 8] \cap \mathbb{Z} \wedge l \leq r \wedge d \leq u \]

这个状态表示在这个棋盘中，从左下角 \((l, d)\) 到右上角 \((r, u)\) 所构成的矩形被拆成 \(i\) 个矩形后平方和最小值。

我们将 \(f_{1, l, d, r, u}\) 初始化为 \((l, d) \rightarrow (r, u)\) 这个矩形的总分平方和。

对于一个矩形，我们只能横切或竖切分割成两个矩形，于是可以得到下列动态转移方程：

\[ \begin{cases} f_{i, l, d, r, u} = \min \limits_{l \leq j \leq r} \{ f_{i - 1, l, d, j, u} + f_{1, j + 1, d, r, u}, f_{1, l, d, j, u} + f_{i - 1, j + 1, d, r, u} \} \\ f_{i, l, d, r, u} = \min \limits_{l \leq j \leq r} \{ f_{i - 1, l, d, r, j} + f_{1, l, j + 1, r, u}, f_{1, l, d, r, j} + f_{i - 1, l, j + 1, r, u} \} \end{cases} \]

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <cstring>
#include <iostream>

const int MAXB = 8, MAXN = 15;

int n;
int board[MAXB + 1][MAXB + 1], s[MAXB + 1][MAXB + 1];
int f[MAXN + 1][MAXB + 1][MAXB + 1][MAXB + 1][MAXB + 1];

inline int getTri(int l, int d, int r, int u) {
    return s[r][u] - s[r][d - 1] - s[l - 1][u] + s[l - 1][d - 1];
}

inline int pow(int x) {
    return x * x;
}

inline void init() {
    memset(s, 0, sizeof(s));
    memset(f, 0x3f, sizeof(f));

    for (int i = 1; i <= MAXB; i++) {
        for (int j = 1; j <= MAXB; j++) {
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + board[i][j];
        }
    }

    for (int l = 1; l <= MAXB; l++) {
        for (int d = 1; d <= MAXB; d++) {
            for (int r = l; r <= MAXB; r++) {
                for (int u = d; u <= MAXB; u++) {
                    f[1][l][d][r][u] = pow(getTri(l, d, r, u));
                }
            }
        }
    }
}

inline void dp() {
    for (int i = 2; i <= n; i++) {
        for (int l = 1; l <= MAXB; l++) {
            for (int d = 1; d <= MAXB; d++) {
                for (int r = l; r <= MAXB; r++) {
                    for (int u = d; u <= MAXB; u++) {
                        for (int j = l; j < r; j++) f[i][l][d][r][u] = std::min(f[i][l][d][r][u], std::min(f[i - 1][l][d][j][u] + f[1][j + 1][d][r][u], f[1][l][d][j][u] + f[i - 1][j + 1][d][r][u]));
                        for (int j = d; j < u; j++) f[i][l][d][r][u] = std::min(f[i][l][d][r][u], std::min(f[i - 1][l][d][r][j] + f[1][l][j + 1][r][u], f[1][l][d][r][j] + f[i - 1][l][j + 1][r][u]));
                    }
                }
            }
        }
    }
}

int main() {
    std::cin >> n;
    for (int i = 1; i <= MAXB; i++) {
        for (int j = 1; j <= MAXB; j++) {
            scanf("%d", &board[i][j]);
        }
    }

    init();

    dp();

    std::cout << f[n][1][1][MAXB][MAXB] << std::endl;

    return 0;
}