[noi1999] 棋盘分割

因为人在学校时间比较要紧就写简单一些

题面: P5752 [NOI1999] 棋盘分割

这道题自己没想出来，结合 zsh 的 ppt 和洛谷上的题解才搞明白

这道题涉及到分割和最值，所以目标就锁定在区间dp，在想dp之前也有几个要处理的问题

1.数学问题#

这道题要求标准差，但是因为有根号很难搞，所以可以先用方差算

s^2 = (\frac{1}{n} \sum^n_{i = 1}{x_i^2}) - \bar x^2\\ \sigma = \sqrt {s^2}

这样只需求出 $\sum_{i = 1}^{n}{x_i^2}$ 再套公式即可求出答案

2.二维前缀和#

因为这道题需要多次计算一个块内的权值的和，维护一个二维的前缀和会很方便，复习一下

维护前缀和

1
for (int i = 1; i <= n; ++i) {
2
  for (int j = 1; j <= n; ++j) {
3
        s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
4
  }
5
}

计算从 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的前缀和

1
int get_sum(int x1, int y1, int x2, int y2) {
2
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
3
}

3.区间dp#

思路

dp的大致思路是维护每一个二维区间内分割 $k$ 次后每一块的总和的平方除以 $n$ 后的结果的和的最小值，目标是 f[1][1][8][8][k]，结果是 sqrt(f[1][1][8][8][n] - ave * ave。（ave 为平均值 $\bar x$ ）
状态

表示一个二维区间至少需要 $4$ 个参数(左上角坐标和右下角坐标)，所以 $f$ 数组要开五维，即 f[9][9][9][9][15]，

f[x1][y1][x2][y2][k]表示从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 这段区间内分割 $k$ 次后每个子区间的权值和 $s$ 的 $\frac{s^2}{n}$ 的和的最小值

重点 ——枚举分割点

因为只能砍成两半，所以可以分别枚举横向分割的分割点的纵坐标和纵向分割的分割点的横坐标，然后状态转移

1
for (int t = x1; t < x2; ++t) { // 枚举纵坐标
2
    f[x1][y1][x2][y2][k] = min(f[x1][y1][x2][y2][k],
3
        min(f[t + 1][y1][x2][y2][k - 1] + getf(x1, y1, t, y2), // 上侧已被分割 k - 1 次
4
            f[x1][y1][t][y2][k - 1] + getf(t + 1, y1, x2, y2))); // 下侧已被分割 k - 1 次
5
}
6
for (int t = y1; t < y2; ++t) { // 枚举横坐标
7
    f[x1][y1][x2][y2][k] = min(f[x1][y1][x2][y2][k],
8
        min(f[x1][t + 1][x2][y2][k - 1] + getf(x1, y1, x2, t), // 左侧已被分割 k - 1 次
9
            f[x1][y1][x2][t][k - 1] + getf(x1, t + 1, x2, y2))); // 右侧已被分割 k - 1 次
10
}

其中 getf 为

1
double getf(int x1, int y1, int x2, int y2) {
2
    double tmp = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
3
    return tmp * tmp / n;
4
}

最后看一下代码我就知道你写不出来#

1
#include <cstdio>
2
#include <cmath>
3
#include <algorithm>
4

5
using namespace std;
6

7
int a[9][9];
8
double s[9][9], f[9][9][9][9][15];
9
int n;
10

11
double getf(int x1, int y1, int x2, int y2) {
12
    double tmp = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
13
    return tmp * tmp / n;
14
}
15

16
int main() {
17
    scanf("%d", &n);
18
    for (int i = 1; i <= 8; ++i) {
19
        for (int j = 1; j <= 8; ++j) {
20
            scanf("%d", &a[i][j]);
21
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j -  1] - s[i - 1][j - 1]; // 二维前缀和
22
        }
23
    }
24
    double ave = s[8][8] / n;
25
    for (int k = 1; k <= n; ++k) {
26
        for (int x2 = 1; x2 <= 8; ++x2) {
27
            for (int y2 = 1; y2 <= 8; ++y2) {
28
                for (int x1 = 1; x1 <= x2; ++x1) { // x1 <= x2 y1 <= y2 这样枚举会快一点
29
                    for (int y1 = 1; y1 <= y2; ++y1) {
30
                        if (k == 1) { // 记得初始化
31
                            f[x1][y1][x2][y2][k] = getf(x1, y1, x2, y2);
32
                            continue;
33
                        }
34
                        f[x1][y1][x2][y2][k] = 0x3f3f3f3f; // 记得初始化
35
                        // 注意区间不要重叠
36
                        for (int t = x1; t < x2; ++t) { // 枚举纵坐标
37
                            f[x1][y1][x2][y2][k] = min(f[x1][y1][x2][y2][k],
38
                                                       min(f[t + 1][y1][x2][y2][k - 1] + getf(x1, y1, t, y2), // 上侧已被分割 k - 1 次
39
                                                           f[x1][y1][t][y2][k - 1] + getf(t + 1, y1, x2, y2))); // 下侧已被分割 k - 1 次
40
                        }
41
                        for (int t = y1; t < y2; ++t) { // 枚举横坐标
42
                            f[x1][y1][x2][y2][k] = min(f[x1][y1][x2][y2][k],
43
                                                       min(f[x1][t + 1][x2][y2][k - 1] + getf(x1, y1, x2, t), // 左侧已被分割 k - 1 次
44
                                                           f[x1][y1][x2][t][k - 1] + getf(x1, t + 1, x2, y2))); // 右侧已被分割 k - 1 次
45
                        }
46
                    }
47
                }
48
            }
49
        }
50
    }
51
    printf("%.3lf\n", sqrt(f[1][1][8][8][n] - ave * ave)); // 输出结果
52
}

Star's Blog

1.数学问题#

2.二维前缀和#

3.区间dp#

最后看一下代码 我就知道你写不出来#

最后看一下代码我就知道你写不出来#