[HAOI2009] 巧克力

题意

有一块 n x m 的巧克力，要把它切成 n x m 个 1 x 1 小块。

一共有：

n-1 条横线，每条横切代价分别是 y_i
m-1 条竖线，每条竖切代价分别是 x_i

每条线最终都必须切一次。
但一条线在某一时刻切下去时，需要乘上当前被另一方向分成了多少块。

要求最小化总切割代价。

思路

先看一个最直接的小数据暴力：

cpp

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#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> x, y;
vector<int> order;  // 0 表示横切，1 表示竖切
long long ans = (1LL << 62);

void dfs(int used_row, int used_col, long long row_piece, long long col_piece, long long cost) {
    if (used_row == n - 1 && used_col == m - 1) {
        ans = min(ans, cost);
        return;
    }

    if (used_row < n - 1) {
        dfs(used_row + 1, used_col, row_piece + 1, col_piece, cost + y[used_row] * col_piece);
    }
    if (used_col < m - 1) {
        dfs(used_row, used_col + 1, row_piece, col_piece + 1, cost + x[used_col] * row_piece);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    y.resize(max(0, n - 1));
    x.resize(max(0, m - 1));

    for (int i = 0; i < n - 1; i++) {
        cin >> y[i];
    }
    for (int i = 0; i < m - 1; i++) {
        cin >> x[i];
    }

    sort(y.begin(), y.end(), greater<long long>());
    sort(x.begin(), x.end(), greater<long long>());

    dfs(0, 0, 1, 1, 0);
    cout << ans << '\n';
    return 0;
}

brute.cpp 会枚举整个切割顺序：

当前选一条横线切
或选一条竖线切

并累计当前代价，最后取最小值。

这个思路很符合题意，但切割顺序总数太多，显然不能用于大数据。

第一步：看清一刀的真实代价

如果当前去切一条横线，代价不是单纯的 y_i，而是：

y_i * 当前纵向块数

因为这一刀要在所有纵向分块上都切一遍。

同理，如果当前切一条竖线，代价是：

x_i * 当前横向块数

第二步：为什么要优先切大的代价

关键观察是：

随着切割进行，横向块数和纵向块数只会越来越大
所以某条线如果晚切，它乘上的系数只会更大

那么一个很自然的想法就是：

代价大的线，应该尽量早切

这样它乘上的系数更小。

这就是贪心策略的核心。

第三步：交换论证

假设当前有两刀可选：

一条横线代价 a
一条竖线代价 b

设当前横向块数是 r，纵向块数是 c。

如果先切横线再切竖线，总代价是：

a * c + b * (r + 1)

如果先切竖线再切横线，总代价是：

b * r + a * (c + 1)

两者相减：

[a * c + b * (r + 1)] - [b * r + a * (c + 1)] = b - a

所以：

当 a > b 时，先切横线更优
当 b > a 时，先切竖线更优

也就是说，谁的代价更大，就应该先切谁。

第四步：做法整理

于是把所有横切代价、竖切代价分别从大到小排序，然后像归并一样扫一遍：

比较当前最大的横切代价和竖切代价
谁更大，就先切谁
更新答案和当前块数

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int n, m;
long long x[MAXN];
long long y[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n - 1; i++) {
        cin >> y[i];
    }
    for (int i = 1; i <= m - 1; i++) {
        cin >> x[i];
    }

    sort(y + 1, y + n, greater<long long>());
    sort(x + 1, x + m, greater<long long>());

    int i = 1;
    int j = 1;
    long long row_piece = 1;  // 当前被横切后有多少块横向条带
    long long col_piece = 1;  // 当前被竖切后有多少块纵向条带
    long long ans = 0;

    while (i <= n - 1 && j <= m - 1) {
        if (y[i] > x[j]) {
            ans += y[i] * col_piece;
            row_piece++;
            i++;
        } else {
            ans += x[j] * row_piece;
            col_piece++;
            j++;
        }
    }

    while (i <= n - 1) {
        ans += y[i] * col_piece;
        i++;
    }
    while (j <= m - 1) {
        ans += x[j] * row_piece;
        j++;
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n \log n + m \log m)$
空间复杂度： $O(n + m)$

总结

这题最核心的不是“怎么模拟切割”，而是先意识到：

每一刀的代价会被另一方向的块数放大
大的代价应该尽早支付

一旦想清楚这一点，题目就变成了一个非常标准的“排序 + 贪心合并”问题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

第一步：看清一刀的真实代价

第二步：为什么要优先切大的代价

第三步：交换论证

第四步：做法整理

代码

复杂度

总结

一图流解析