「一本通 1.3 例 2」生日蛋糕

形式化题目

制作一个由 $M$ 层同心圆柱组成的蛋糕，总积为 $N\pi$ 。各层圆柱自底向上编号为第 $M$ 层至第 $1$ 层，其半径 $R_i$ 与高度 $H_i$ （ $1 \le i \le M$ ）均为正整数，且满足严格单调递减：

R_M > R_{M-1} > \dots > R_1 \ge 1

H_M > H_{M-1} > \dots > H_1 \ge 1

总表面积（不计最底层圆柱的下底面）为

Q = S\pi

。求在满足

\sum_{i=1}^M R_i^2 H_i = N

的前提下，

S

的最小值；若无解则输出

0

。

正解

思路

1. 表面积的等价转化

蛋糕向外暴露的表面积由两部分组成：

各层圆柱的侧面积之和： $\sum_{i=1}^M 2 R_i H_i$ 。
各层暴露在外的上表面之和：从蛋糕正上方垂直俯视，上方较小圆柱投影全部落在下方圆柱之上，各层露出的环形区域面积加上顶层圆面积，其总投影恰好等于最底层圆柱的底面积 $R_M^2$ 。

因此总表面积系数可统一表示为：

S = R_M^2 + \sum_{i=1}^M 2 R_i H_i

仅需在最底层决策时累加一次

R_M^2

，其余各层只需统计侧面积

2 R_i H_i

。

2. 搜索顺序优化

选择自底向上（从第 $M$ 层到第 $1$ 层）进行深度优先搜索：

底层圆柱半径与高度大、占据体积大，分支数量少；
尽早确定底层的大尺寸，能在搜索早期迅速逼近较优的表面积解，从而使后续的最优性剪枝更为严格；
在枚举每一层的半径 $R$ 和高度 $H$ 时，按从大到小的顺序逆序枚举。

3. 剪枝策略

在搜索递归函数 dfs(layer, v, s, r_prev, h_prev) 中，设当前需要确定第 $layer$ 层，剩余所需总体积为 $v$ ，当前已消耗的表面积为 $s$ ：

可行性剪枝（最小体积下界）：剩余 $1 \sim layer$ 层满足整数严格递减，其半径与高度至少为 $1, 2, \dots, layer$ 。这些层所能构成的最小体积为 $\min V(layer) = \sum_{k=1}^{layer} k^3$ 。若当前剩余体积 $v < \min V(layer)$ ，后续必定无法构造出合法的 $layer$ 层，直接回溯。
最优性剪枝（最小侧面积下界）：同理，剩余 $1 \sim layer$ 层的最小累计侧面积为 $\min S(layer) = \sum_{k=1}^{layer} 2k^2$ 。若 $s + \min S(layer) \ge best\_s$ ，即使后续每层均取理论最小侧面积也无法超越已知最优解，直接回溯。
核心数学剪枝（剩余体积与侧面积关系估价）：设剩余 $1 \sim layer$ 层的实际体积为 $v = \sum_{k=1}^{layer} R_k^2 H_k$ ，对应的侧面积为 $S_{rem} = \sum_{k=1}^{layer} 2 R_k H_k$ 。由于半径严格递减，对任意 $1 \le k \le layer$ ，均有 $R_k < R_{prev}$ 。因此：
$S_{rem} = \sum_{k=1}^{layer} \frac{2 R_k^2 H_k}{R_k} > \frac{2}{R_{prev}} \sum_{k=1}^{layer} R_k^2 H_k = \frac{2v}{R_{prev}}$
这意味着剩余层至少还会带来超过 $\frac{2v}{R_{prev}}$ 的侧面积增量。若满足 $s + \lfloor\frac{2v}{R_{prev}}\rfloor \ge best\_s$ ，当前分支必然劣于最优解，直接剪枝。
上下界约束收紧：
- 半径上限： $R \le \min\left(r_{prev} - 1, \left\lfloor\sqrt{\frac{v - \min V(layer - 1)}{layer}}\right\rfloor\right)$ ；下限： $R \ge layer$ 。
- 高度上限： $H \le \min\left(h_{prev} - 1, \left\lfloor\frac{v - \min V(layer - 1)}{R^2}\right\rfloor\right)$ ；下限： $H \ge layer$ 。

graph TD
    A[进入 dfs(layer, v, s)] --> B{v < min_v[layer]?}
    B -- 是 --> CUT1[可行性剪枝: 剩余体积不足]
    B -- 否 --> C{s + min_s[layer] >= best_s?}
    C -- 是 --> CUT2[最优性剪枝: 最小侧面积超限]
    C -- 否 --> D{s + 2*v/r_prev >= best_s?}
    D -- 是 --> CUT3[数学估价剪枝: 侧面积理论下界超限]
    D -- 否 --> E[计算 R, H 紧确上下界]
    E --> F[从大到小枚举 R, H 递归进入下一层]

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 10:48
# update_at: 2026-09-30 11:15

import math
import sys

INF = 10**9


def search_cake(n: int, m: int) -> int:
    """搜索满足体积限制与单调递减约束的 M 层蛋糕最小表面积。"""
    # 预处理从顶层往下数前 i 层的最小累计体积与最小累计侧面积
    min_v = [0] + [sum(k * k * k for k in range(1, i + 1)) for i in range(1, m + 1)]
    min_s = [0] + [sum(2 * k * k for k in range(1, i + 1)) for i in range(1, m + 1)]

    best_s = INF

    def dfs(layer: int, v: int, s: int, r_prev: int, h_prev: int) -> None:
        """从下往上递归搜索第 layer 层，v 为剩余体积，s 为当前累计面积。"""
        nonlocal best_s
        if layer == 0:
            if v == 0 and s < best_s:
                best_s = s
            return

        # 剪枝 1：剩余体积不足以搭建剩余层
        # 剪枝 2：当前面积加上剩余最小侧面积仍劣于最优解
        # 剪枝 3：剩余体积换算侧面积下界 2 * v / r_prev 加上当前面积仍劣于最优解
        if v < min_v[layer] or s + min_s[layer] >= best_s or s + 2 * v // r_prev >= best_s:
            return

        # 半径上下界：必须严格小于上一层，且为剩余层预留最小高度 1
        max_r = min(r_prev - 1, int(math.isqrt((v - min_v[layer - 1]) // layer)))
        for r in range(max_r, layer - 1, -1):
            max_h = min(h_prev - 1, (v - min_v[layer - 1]) // (r * r))
            for h in range(max_h, layer - 1, -1):
                cur_v = r * r * h
                cur_s = 2 * r * h
                dfs(layer - 1, v - cur_v, s + cur_s, r, h)

    # 第 M 层（最底层）确定底面积 r^2 并启动搜索
    max_r_m = int(math.isqrt(n))
    for r in range(max_r_m, m - 1, -1):
        if r * r + min_s[m] >= best_s:
            continue
        max_h = (n - min_v[m - 1]) // (r * r)
        for h in range(max_h, m - 1, -1):
            cur_v = r * r * h
            cur_s = r * r + 2 * r * h
            if cur_s + min_s[m - 1] >= best_s or cur_s + 2 * (n - cur_v) // r >= best_s:
                continue
            dfs(m - 1, n - cur_v, cur_s, r, h)

    return best_s if best_s != INF else 0


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    m = next(data)
    ans = search_cake(n, m)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 01:16
 * update_at: 2026-10-05 01:16
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXM = 25;
const ll INF = 1e9;

ll n, m;
ll min_v[MAXM]; // min_v[i] 表示自顶向下 i 层都取最小尺寸时的最小体积和 sum_{k=1}^{i} k^3
ll min_s[MAXM]; // min_s[i] 表示自顶向下 i 层都取最小尺寸时的最小侧面积和 sum_{k=1}^{i} 2*k^2
ll best_s;      // 当前搜到的最小表面积系数 S

// 返回 floor(sqrt(x))，用整数二分求值，避免浮点误差和类型转换。
ll isqrt_ll(ll x) {
    if (x <= 0) return 0;
    ll lo = 1, hi = x, ans = 0;
    while (lo <= hi) {
        ll mid = (lo + hi) / 2;
        // 用 mid <= x / mid 代替 mid*mid <= x，避免乘法溢出
        if (mid <= x / mid) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

// 自底向上搜索：正在确定第 layer 层，剩余体积为 v，已累计表面积系数为 s，
// r_prev 与 h_prev 是刚确定的更低一层的半径和高度（必须严格更大）。
void dfs(ll layer, ll v, ll s, ll r_prev, ll h_prev) {
    if (layer == 0) {
        if (v == 0 && s < best_s) best_s = s;
        return;
    }
    // 剪枝 1：剩余体积不足以填满剩余层
    if (v < min_v[layer]) return;
    // 剪枝 2：加上剩余层的最小侧面积仍不优于当前最优解
    if (s + min_s[layer] >= best_s) return;
    // 剪枝 3：剩余体积换算出的侧面积下界 2*v/r_prev 已无法更优
    if (s + 2 * v / r_prev >= best_s) return;

    ll v_left = v - min_v[layer - 1]; // 当前层与更低层可分配的体积
    ll max_r = isqrt_ll(v_left / layer); // 半径上限：保证剩余层每层至少留 1 的高度
    if (r_prev - 1 < max_r) max_r = r_prev - 1;
    for (ll r = max_r; r >= layer; r--) {
        ll max_h = v_left / (r * r);
        if (h_prev - 1 < max_h) max_h = h_prev - 1;
        for (ll h = max_h; h >= layer; h--) {
            dfs(layer - 1, v - r * r * h, s + 2 * r * h, r, h);
        }
    }
}

// 先枚举最底层（第 m 层）的半径与高度，最底层的底面积 R^2 只在此时计入一次。
void solve() {
    best_s = INF;
    ll max_r_m = isqrt_ll(n);
    for (ll r = max_r_m; r >= m; r--) {
        if (r * r + min_s[m] >= best_s) continue;
        ll max_h = (n - min_v[m - 1]) / (r * r);
        for (ll h = max_h; h >= m; h--) {
            ll cur_v = r * r * h;
            ll cur_s = r * r + 2 * r * h;
            if (cur_s + min_s[m - 1] >= best_s) continue;
            if (cur_s + 2 * (n - cur_v) / r >= best_s) continue;
            dfs(m - 1, n - cur_v, cur_s, r, h);
        }
    }
    if (best_s == INF) cout << 0 << endl;
    else cout << best_s << endl;
}

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

    cin >> n >> m;

    // 预处理最小体积和与最小侧面积和，供剪枝使用
    min_v[0] = 0;
    min_s[0] = 0;
    for (ll i = 1; i <= m; i++) {
        min_v[i] = min_v[i - 1] + i * i * i;
        min_s[i] = min_s[i - 1] + 2 * i * i;
    }

    solve();

    return 0;
}

复杂度

时间复杂度：虽然未经剪枝的状态空间规模极大，但在体积下界、侧面积下界、数学估价不等式以及紧确范围约束的联合剪枝下，搜索树绝大多数无效分支在浅层即被截断。在 $N \le 10000, M \le 20$ 的约束下，实际访问的状态节点数极少，单用例在 Python 3 下运行时间不超过 $30\text{ ms}$ 。
空间复杂度：递归栈深度至多为 $M \le 20$ 层，预处理数组长度为 $O(M)$ ，辅助空间复杂度为 $O(M)$ 。

总结

本题是深度优先搜索与数学不等式剪枝的经典范例：

投影转化将表面积问题简化为“最底层底面积 + 侧面积总和”；
逆序搜索自大而小展开，尽早收敛最优解上限；
利用 $S_{rem} > \frac{2v}{R}$ 将体积直接转化为未来侧面积的理论紧确下界，构成了截断深层分支的最有效利刃。

「一本通 1.3 例 2」生日蛋糕

目录

形式化题目

正解

思路

1. 表面积的等价转化

2. 搜索顺序优化

3. 剪枝策略

代码

复杂度

总结