形式化题目

需要选出 $M$ 组正整数 $(R_1,H_1),\dots,(R_M,H_M)$（下标自下而上），满足两个条件：

并使目标函数

最小。$R_1^2$ 是最底层的顶面圆面积，$2R_iH_i$ 是第 $i$ 层的侧面（展开后是宽 $2\pi R_i$、高 $H_i$ 的矩形）；最下层的下底面不涂奶油，所以不出现在 $S$ 里。若不存在任何合法方案，输出 $0$（题目把它也写成"$S=0$"）。

正解

思路

先看搜索空间有多大。 最直接的想法是自底向上逐层枚举 $(R_i,H_i)$：第 $i$ 层的半径、高度必须小于上一层，所以把 r_max、h_max 当作 DFS 参数往下传就行。但 $R_1 \leqslant \lfloor\sqrt{N}\rfloor \leqslant 100$、$H_1 \leqslant N \leqslant 10^4$，第一层就有 $10^6$ 量级的组合，$M=20$ 时完全不可行。瓶颈很明确：枚举树绝大部分分支注定凑不出体积 $N$、或者注定不会比已有答案更优，必须在进入分支之前就把它们砍掉。

先固定"每层最小尺寸"这个下界。 $M$ 层的半径必须严格递减且都是正整数，所以最省也要占到 $1,2,\dots,M$ 这些半径，高度同理；反过来，从下往上第 $j$ 层上面还有 $j-1$ 层，半径至少要 $j$。两个方向合起来说明：从下往上数第 $j$ 层，半径和高度最小都是 $j$。于是"剩下 left 层"的蛋糕，体积和侧面积各有一个与已选层完全无关的绝对下界：

这两个前缀和只算一次，DFS 里 $O(1)$ 查询。下图是 $M=4$ 时最省材料的那套尺寸，任何合法方案都不会比它更"矮胖"：

1
2
3
4
5最小可行尺寸的剖面（第 j 层 R=H=j，上窄下宽）：
+-----------+   第 4 层 R=H=4
 +---------+   第 3 层 R=H=3
  +-------+   第 2 层 R=H=2
   +-----+   第 1 层 R=H=1

图里每一层都比上面一层宽一格以上，这正是严格递减约束的几何含义。读者要观察的是：层数 $j$ 越大、允许的尺寸越小，所以越靠上的层反而越省；这解释了为什么下界是 $\sum j^3$ 而不是 $M\cdot 1^3$。把这些下界按层数列出来，就是 DFS 里随手要用的查询表：

表的最后一列是本题最狠的一条信息：$M=12$ 时体积下界已经到 $6084$，意味着 $N$ 稍小就直接无解——这正是 solve 开头那句 $\text{minV}[M] > N$ 的由来。

于是三条剪枝。 记 left 为含当前层在内还要放的层数、rest 为还要填的体积、area 为已累计的侧面积、best 为当前最优 $S$：

1. 体积可行性：vol + minV[left] > N 时这条分支无论如何都凑不满（连最省都超了），直接返回。
2. 侧面积下界：area + minS[left] >= best 时，即使剩余层全部取到理论最小侧面积也追不上 best，直接返回。注意后续层的顶面本来就不计入 $S$，所以 $\text{minS}$ 确实是一个不丢最优解的下界。
3. 剩余体积的侧面积下界：把还要填的体积 rest 全部摊成一根半径为 $R_{\max}$ 的柱体时侧面积最小，为 $2\,\text{rest}/R_{\max}$。理由是把 rest 拆成若干层 $v_j = R_j^2H_j$ 后，第 $j$ 层贡献的侧面积是 $2R_jH_j = 2v_j/R_j \geqslant 2v_j/R_{\max}$（因为 $R_j \leqslant R_{\max}$），逐层相加即得。于是 area + 2*rest/r_max >= best 时剪枝；代码里通分成 area * r_max + 2 * rest >= best * r_max，避免除法与浮点误差。

第 3 条比第 2 条强在它是动态的：rest 随搜索深入不断变小，搜索早期它比第 2 条松，但到了深层次几乎能立刻判定"再怎么填也追不上 best"，而第 2 条只看层数、与已填体积无关。

剪枝 1 必须写成"跳过"而不是"跳出"。 这是本题最容易踩的坑。在同一半径下增加高度，体积单调变大，所以高度循环里体积超了可以 break；但不同半径之间体积不可比——半径从 $r$ 减小时，即使高度不变，$r^2h$ 也会先掉下去再重新涨上来。第一版实现里在半径循环用了 break，$N=4999$、$M=8$ 直接输出 0。因此代码里对半径用 continue，高度循环才交给 h_top 上界自动收住。

三个让搜索变快的实现细节。

• 给上层留够体积。 本层高度不只是 $H_i \leqslant H_{i-1}-1$，还必须保证上面 $left-1$ 层放得下，于是
  $$H_i \leqslant \Big\lfloor \frac{rest - \text{minV}[left-1]}{R_i^2} \Big\rfloor,$$
  这就是代码里的 h_top。不加这一条，高度循环会白跑大量注定被剪的取值。
• 最后一层直接解方程。 只剩一层时必须有 $R^2 \mid rest$，高度 $rest/R^2$ 由除法唯一确定，只需枚举 $R$；而 $R^2$ 关于 $R$ 单调，所以 if r*r > rest: continue 之外还能顺带收紧。这一条把最深的递归层换成了 $O(R_{\max})$ 的循环。
• $best$ 的初值。 代码取 inf = 3 * n + 1 当"无解"哨兵。任何可行方案都满足 $S \leqslant 3N$：由 $R_i \geqslant 1$、$H_i \geqslant 1$ 得 $2R_iH_i \leqslant 2R_i^2H_i$，又 $R_1^2 \leqslant R_1^2H_1$，相加得 $S \leqslant 3\sum R_i^2H_i = 3N$。这个初值既大于一切可能的答案（保证剪枝 2、3 不误杀），又能让"始终没找到方案"通过 best == inf 分辨出来。

枚举顺序也有讲究：半径、高度都从大到小。 体积大的分支先试，能更快把 best 压小，从而让剪枝 2、3 更早生效。但不能因此只试少数几个大半径：$N=10000$、$M=1$ 的最优解是 $R=20,H=25$（$S=1400$），而半径最大的 $R=100,H=1$ 给出的是 $10200$——半径大反而更费顶面积。所以半径仍然必须完整枚举，只是顺序从大到小。

代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84#!/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-10-01 13:29
# update_at: 2026-10-01 13:29

import sys
from math import isqrt


def packing_min(k: int) -> tuple[list[int], list[int]]:
    """占满 k 层时体积与侧面积的绝对下界前缀和：从下往上第 j 层至少有半径、高度 j。

    k 层的半径必须严格递减，所以再省也要占到 1,2,...,k 这些半径，高度同理；
    于是 min_v[k] = sum(j^3)、min_s[k] = sum(2*j^2) 就是剩余层数对应的最小值。
    """
    min_v = [0] * (k + 1)
    min_s = [0] * (k + 1)
    for j in range(1, k + 1):
        min_v[j] = min_v[j - 1] + j ** 3
        min_s[j] = min_s[j - 1] + 2 * j ** 2
    return min_v, min_s


def solve() -> None:
    """自底向上 DFS 枚举每层的 (R, H)，用三条下界剪枝，取最小的 S。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    min_v, min_s = packing_min(m)
    if min_v[m] > n:  # 连最省体积的 1,2,...,m 都塞不进 N，直接无解
        print(0)
        return

    # 任意可行方案的 S <= 3N（见正文证明），取 3N+1 当"无解"哨兵，也当剪枝的初始上界
    inf = 3 * n + 1
    best = inf

    def dfs(level: int, vol: int, area: int, r_max: int, h_max: int) -> None:
        """已放好 level-1 层、占用体积 vol、侧面积 area，下一层半径、高度上界为 r_max/h_max。"""
        nonlocal best
        left = m - level + 1  # 含本层在内还要放几层
        rest = n - vol        # 还要填的体积

        if area + min_s[left] >= best:  # 下界一：剩余层的侧面积不可能比 min_s 更小
            return
        # 下界二：剩余体积的侧面积至少是 2*rest/r_max（把余下体积摊成一根半径 r_max 的柱），
        # 通分后避免除法与浮点误差。
        if area * r_max + 2 * rest >= best * r_max:
            return

        if left == 1:  # 最后一层：体积必须整除 r^2，直接算高度，不必再开一层递归
            for r in range(r_max, 0, -1):
                square = r * r
                if rest % square:
                    continue
                h = rest // square
                if h > h_max:
                    continue
                area_now = area + 2 * r * h + (square if level == 1 else 0)
                if area_now < best:
                    best = area_now
            return

        for r in range(r_max, left - 1, -1):  # 本层半径至少 left，否则上面放不下 left-1 层
            square = r * r
            base = area + (square if level == 1 else 0)  # 顶面积只在下底面那一层计入
            if base * r + 2 * rest >= best * r:  # 同样的侧面积下界，先从 r 上砍掉
                continue
            # 本层高度留给上层 min_v[left-1] 的体积，上界由此收紧
            h_top = min(h_max, (rest - min_v[left - 1]) // square)
            for h in range(h_top, left - 1, -1):
                area_now = base + 2 * r * h
                if area_now + min_s[left - 1] >= best:  # 本层定下后重新估一次下界
                    continue
                dfs(level + 1, vol + square * h, area_now, r - 1, h - 1)

    dfs(1, 0, 0, isqrt(n), n)
    print(0 if best == inf else best)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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-06 17:13
 * update_at: 2026-10-06 17:14
 */
// 生日蛋糕：自底向上 DFS 枚举每层的 (R, H)，三条下界剪枝，求最小外表面积 S。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 25;

ll n;              // 蛋糕体积为 n*pi
ll m;              // 蛋糕层数
ll min_v[MAXM];    // min_v[left]：再放 left 层所需体积的绝对下界 sum(j^3)
ll min_s[MAXM];    // min_s[left]：再放 left 层侧面积的绝对下界 sum(2*j^2)
ll best;           // 当前最优答案 S；3n+1 当无解哨兵（任何可行方案 S <= 3n）

// 自底向上第 j 层半径、高度至少为 j（严格递减 + 正整数），
// 由此得到剩余 left 层的体积 / 侧面积下界前缀和。
void init_min() {
    min_v[0] = 0;
    min_s[0] = 0;
    for (ll j = 1; j <= m; j++) {
        min_v[j] = min_v[j - 1] + j * j * j;
        min_s[j] = min_s[j - 1] + 2 * j * j;
    }
}

// 已放好 level-1 层，占用体积 vol、侧面积 area（不含底面），
// 下一层的半径上界 r_max、高度上界 h_max。
// left = 含本层在内还要放的层数，rest = 还要填的体积。
void dfs(ll level, ll vol, ll area, ll r_max, ll h_max) {
    ll left = m - level + 1;
    ll rest = n - vol;

    // 剪枝一：剩余层即使全取最小尺寸，侧面积也追不上 best
    if (area + min_s[left] >= best) return;
    // 剪枝二：剩余体积摊成半径 r_max 的柱体侧面积最小，为 2*rest/r_max；
    // 通分成乘法，避免除法与浮点误差
    if (area * r_max + 2 * rest >= best * r_max) return;

    // 最后一层：体积必须整除 r^2，高度由除法唯一确定，不必再递归
    if (left == 1) {
        for (ll r = r_max; r >= 1; r--) {
            ll square = r * r;
            if (rest % square != 0) continue;
            ll h = rest / square;
            if (h > h_max) continue;
            ll area_now = area + 2 * r * h;
            if (level == 1) area_now += square; // 最底层顶面计入 S
            if (area_now < best) best = area_now;
        }
        return;
    }

    // 半径从大到小枚举：大体积分支先试，更快压小 best；本层半径至少 left
    for (ll r = r_max; r >= left; r--) {
        ll square = r * r;
        ll base = area;
        if (level == 1) base += square; // 顶面积只在最底层计入
        // 与剪枝二同理，先在半径维度上砍掉
        if (base * r + 2 * rest >= best * r) continue;

        // 本层高度还要给上面 left-1 层留出 min_v[left-1] 的体积
        ll h_top = min(h_max, (rest - min_v[left - 1]) / square);
        for (ll h = h_top; h >= left; h--) {
            ll area_now = base + 2 * r * h;
            // 本层定下后重新估一次侧面积下界
            if (area_now + min_s[left - 1] >= best) continue;
            dfs(level + 1, vol + square * h, area_now, r - 1, h - 1);
        }
    }
}

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

    cin >> n >> m;
    init_min();
    if (min_v[m] > n) { // 连最省体积的 1,2,...,m 层都放不下，直接无解
        cout << 0 << endl;
        return 0;
    }

    // 任何可行方案 S <= 3n（2R_iH_i <= 2R_i^2H_i，R_1^2 <= R_1^2H_1），
    // 取 3n+1 当无解哨兵，同时是剪枝的初始上界
    best = 3 * n + 1;
    // 第 1 层半径至多 sqrt(n)（体积约束），高度至多 n
    dfs(1, 0, 0, (ll)sqrt((double)n), n);

    if (best == 3 * n + 1) cout << 0 << endl;
    else cout << best << endl;

    return 0;
}

复杂度

• 时间复杂度：理论上仍是级别为 $\prod_i |R_i|\cdot|H_i|$ 的指数搜索，但三条下界把实际访问的节点压得很小。对 $1 \leqslant N \leqslant 10^4$、$1 \leqslant M \leqslant 20$ 的全部 $2\times 10^5$ 组输入做穷举扫描，单组最坏 20ms（$N=6444$、$M=8$），平均约 0.7ms；真实测试数据 5 组最慢 0.024s，远低于 1000ms。
• 空间复杂度：$O(M)$。只有 packing_min 返回的两个长度 $M+1$ 的数组和深度 $M$ 的递归栈；实测峰值 15MB，远低于 128MB。

总结

• 搜索类题目的写法是"先写出完整枚举，再逐条回答’这条分支还有希望吗’"。本题的三个希望来源分别是：体积能不能凑够、侧面积能不能追上最优、剩余体积换算成侧面积还差多少。
• 严格递减 + 正整数立即给出"第 $j$ 层至少 $j$"这条看似不起眼、实则最有效的下界，它同时服务体积和侧面积两条剪枝。
• 剩余体积的侧面积下界 $2\,\text{rest}/R_{\max}$ 是把"体积"换算成"目标函数"的桥梁——很多搜索题找不到剪枝，就是缺这样一次换算。
• 剪枝的方向比剪枝本身更容易错：同一半径下体积单调才允许 break，跨半径只能 continue。

图示解析

下面用样例 $N=100$、$M=2$ 走一遍真实搜索，看看剪枝的实际效果（表由与 main.py 同构的脚本跑出，代码在 problem-analysis-workspace/viz_render.py）。

表的每一行是第一层的一个 $(R_1,H_1)$ 分支，最后一列是该分支结束后全局最优值的变化。读者应观察两点：一是半径从 $7$ 降到 $4$ 的过程中前四行都凑不出第二层，说明真正的难点不是枚举，而是发现"第一层选得太大就再也填不满"；二是答案在第 5 行就被找到（$R_1=4,H_1=6$ 配上 $R_2=2,H_2=1$，$S=16+48+4=68$），此后每一行都被 area + minS[left] >= best 立刻砍掉。同理，$R_1>4$ 的分支被 R_1^2 * r_max + 2 * rest >= best * r_max 这类动态下界提前挡在高度循环之外，所以 $10^6$ 量级的第一层组合实际只访问了几十个节点。