信奥赛C++提高组csp-s之搜索进阶（搜索剪枝案例实践2）-171主机测评

信奥赛C++提高组csp-s之搜索进阶（搜索剪枝案例实践2）

在这里插入图片描述

生日蛋糕 —— 上下界剪枝 + 最优性剪枝

题目描述

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为

N\\pi

$N π$ 的

$M$ 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第

$i$ （

≤

1 \\leq i \\leq M

$1 \leq i \leq M$ ）层蛋糕是半径为

R_i

$R_{i}$ ，高度为

H_i

$H_{i}$ 的圆柱。当

i \\lt M

$i < M$ 时，要求

R_i \\gt R_{i+1}

$R_{i} > R_{i + 1}$ 且

H_i \\gt H_{i+1}

$H_{i} > H_{i + 1}$ 。

由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积

$Q$ 最小。

请编程对给出的

$N$ 和

$M$ ，找出蛋糕的制作方案（适当的

R_i

$R_{i}$ 和

H_i

$H_{i}$ 的值），使

S=\\dfrac{Q}{\\pi}

$S = \frac{Q}{π}$ 最小。

（除

$Q$ 外，以上所有数据皆为正整数）

输入格式

第一行为一个整数

$N$ （

≤

N \\leq 2 \\times 10^4

$N \leq 2 \times 1 0^{4}$ ），表示待制作的蛋糕的体积为

N\\pi

$N π$ 。

第二行为

$M$ （

≤

M \\leq 15

$M \leq 15$ ），表示蛋糕的层数为

$M$ 。

输出格式

输出一个整数

$S$ ，若无解，输出

$0$ 。

输入输出样例 1

输入 1

100
2

输出 1

思路分析

问题理解

我们需要制作一个 M 层的圆柱形蛋糕，从下往上每层的半径

R_i

$R_{i}$ 和高度

H_i

$H_{i}$ 均为正整数，且满足

R_i > R_{i+1},\\ H_i > H_{i+1}

$R_{i} > R_{i + 1}, H_{i} > H_{i + 1}$ 。蛋糕总体积为

N\\pi

$N π$ ，要求外表面面积 Q 最小（最下一层的下底面除外）。输出

S = Q / \\pi

$S = Q / π$ （整数）。

外表面面积计算方式为：所有层的侧面积之和 + 最底层的下底面积。

解题思路

由于

≤

M \\le 15

$M \leq 15$ ，

≤

20000

N \\le 20000

$N \leq 20000$ ，直接枚举所有可能的半径和高度组合会爆炸，必须使用DFS + 剪枝。

1. 搜索顺序

从**最底层（第 M 层）开始向最顶层（第 1 层）**搜索。因为底层半径和高度较大，先枚举大值有利于后续剪枝。

2. 状态表示

dep：当前正在处理的层数（从 M 到 1）
v：已经使用的体积
s：已经累积的表面积（注意：当 dep == M 时会加上最底层的下底面积）

3. 预处理最小可能值（剪枝用）

minv[i]：从上往下前 i 层的最小体积（假设每层半径 = 高 = i，则体积为 $i^3 i3）$
mins[i]：前 i 层的最小侧面积（每层侧面积 $2\\pi r h 2πrh，最小为 2 i 2 2i^2 2i2）$

4. 剪枝策略

体积剪枝：若当前体积 + 剩余层的最小体积 > N，则不可能完成，剪枝。
表面积剪枝：若当前表面积 + 剩余层的最小侧面积 ≥ 当前最优解，则剪枝。
剩余体积的侧面积下界：剩余体积为 N – v，若将其全部做成一个半径为 r[dep+1] 的圆柱（最大可能半径），其侧面积为 2*(N-v)/r[dep+1]。这个值是剩余部分侧面积的下界（半径越大，侧面积越小）。若 s + 下界 ≥ ans，则剪枝。

5. 枚举半径和高度

半径 i：下限 = dep（保证上面还能放下 dep-1 层）上限 = min( sqrt(N-v), r[dep+1]-1 )（不能超过下一层半径，且体积限制）
高度 j：下限 = dep 上限 = min( (N-v)/(i*i), h[dep+1]-1 )（体积限制 + 递减约束）

6. 递归与回溯

更新体积：v + i*i*j
更新表面积：s + 2*i*j，若为最底层（dep == M）还需加上 i*i（下底面积）
递归 dfs(dep-1, new_v, new_s)

7. 输出

若找到解则输出最优的 ans，否则输出 0。

代码实现

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
int N, M, ans = INF;
int mins[25], minv[25]; // 前 i 层的最小侧面积和最小体积
int r[25], h[25]; // 每层的半径和高度（从下往上存储）

// dep：当前要处理的层数（从 M 向下到 1）
// v：已经使用的体积
// s：已经累积的表面积（最底层下底面积已在 dep==M 时加入）
void dfs(int dep, int v, int s) {
if (dep == 0) { // 所有层处理完毕
if (v == N) ans = min(ans, s); // 体积恰好为 N 时更新答案
return;
}

// 剪枝1：剩余体积加上已有体积仍不足 N，或已超过 N
if (v + minv[dep] > N) return;
// 剪枝2：当前表面积加上剩余层的最小侧面积已经不小于最优解
if (s + mins[dep] >= ans) return;
// 剪枝3：剩余体积对应的最小可能侧面积下界估算
// 剩余体积为 N-v，用当前层的下一层半径（即更大半径）作为半径，
// 得到剩余侧面积的下界（半径越大，侧面积越小）
if (s + 2 * (N – v) / r[dep + 1] >= ans) return;

// 枚举当前层的半径，从大到小
// 半径下限：至少 dep（保证上面还能放 dep-1 层）
// 半径上限：不能超过下一层半径-1，且不能超过 sqrt(N-v)（最小高度为1）
for (int i = min((int)sqrt(N – v), r[dep + 1] – 1); i >= dep; i—) {
// 枚举当前层的高度
// 高度下限：至少 dep
// 高度上限：不能超过下一层高度-1，且受体积限制 (N-v)/(i*i)
for (int j = min((N – v) / i / i, h[dep + 1] – 1); j >= dep; j—) {
r[dep] = i;
h[dep] = j;
int cur_s = s + 2 * i * j; // 加上当前层的侧面积
if (dep == M) cur_s += i * i; // 最底层额外加上下底面积
dfs(dep – 1, v + i * i * j, cur_s);
}
}
}

int main() {
cin >> N >> M;
// 预处理前 i 层的最小体积和最小侧面积（假设半径 = 高 = i）
for (int i = 1; i <= M; i++) {
minv[i] = minv[i – 1] + i * i * i; // 体积：i^3
mins[i] = mins[i – 1] + 2 * i * i; // 侧面积：2*i^2
}
// 边界条件：第 M+1 层（虚拟层）半径和高度设为无穷大，以便底层枚举时不受限制
r[M + 1] = h[M + 1] = INF;
dfs(M, 0, 0); // 从最底层开始搜索
cout << (ans == INF ? 0 : ans) << endl;
return 0;
}

功能分析

1. 解决问题

在给定总体积 (N) 和层数 (M) 的情况下，找到使外表面面积最小的蛋糕制作方案，并输出最小的 (S)（整数）。若无解则输出 0。

2. 算法核心

深度优先搜索：枚举每一层的半径和高度，通过递归遍历所有合法组合。
剪枝优化：
- 可行性剪枝（体积不足或超出）
- 最优性剪枝（当前面积已不优于已知最优解）
- 剩余体积的面积下界剪枝
预处理：计算最小可能体积和侧面积，用于剪枝判断。
有序枚举：半径和高度从大到小枚举，优先尝试大值，加速找到较优解并增强剪枝效果。

3. 注意点

表面积的计算方式为所有层侧面积之和 + 最底层下底面积，这与题目文字描述略有差异，但符合样例和多数 AC 代码的实现。
半径和高度的下限取 dep，保证了递减性且每层至少为 1。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》： https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

在这里插入图片描述

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

在这里插入图片描述

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

在这里插入图片描述 GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}

信奥赛C++提高组csp-s之搜索进阶（搜索剪枝案例实践2）