企业官网建设流程全解析

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

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

题目描述

7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为N π N\piNπ的M MM层生日蛋糕，每层都是一个圆柱体。

设从下往上数第i ii（1 ≤ i ≤ M 1 \leq i \leq M1≤i≤M）层蛋糕是半径为R i R_iRi​，高度为H i H_iHi​的圆柱。当i < M i \lt Mi<M时，要求R i > R i + 1 R_i \gt R_{i+1}Ri​>Ri+1​且H i > H i + 1 H_i \gt H_{i+1}Hi​>Hi+1​。

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

请编程对给出的N NN和M MM，找出蛋糕的制作方案（适当的R i R_iRi​和H i H_iHi​的值），使S = Q π S=\dfrac{Q}{\pi}S=πQ​最小。

（除Q QQ外，以上所有数据皆为正整数）

输入格式

第一行为一个整数N NN（N ≤ 2 × 10 4 N \leq 2 \times 10^4N≤2×104），表示待制作的蛋糕的体积为N π N\piNπ。

第二行为M MM（M ≤ 15 M \leq 15M≤15），表示蛋糕的层数为M MM。

输出格式

输出一个整数S SS，若无解，输出0 00。

输入输出样例 1

输入 1

100 2

输出 1

68

思路分析

问题理解

我们需要制作一个M 层的圆柱形蛋糕，从下往上每层的半径R i R_iRi​和高度H i H_iHi​均为正整数，且满足R i > R i + 1 , H i > H i + 1 R_i > R_{i+1},\ H_i > H_{i+1}Ri​>Ri+1​,Hi​>Hi+1​。蛋糕总体积为N π N\piNπ，要求外表面面积Q 最小（最下一层的下底面除外）。输出S = Q / π S = Q / \piS=Q/π（整数）。

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

解题思路

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

1. 搜索顺序

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

2. 状态表示

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

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

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

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>usingnamespacestd;constintINF=0x3f3f3f3f;intN,M,ans=INF;intmins[25],minv[25];// 前 i 层的最小侧面积和最小体积intr[25],h[25];// 每层的半径和高度（从下往上存储）// dep：当前要处理的层数（从 M 向下到 1）// v：已经使用的体积// s：已经累积的表面积（最底层下底面积已在 dep==M 时加入）voiddfs(intdep,intv,ints){if(dep==0){// 所有层处理完毕if(v==N)ans=min(ans,s);// 体积恰好为 N 时更新答案return;}// 剪枝1：剩余体积加上已有体积仍不足 N，或已超过 Nif(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(inti=min((int)sqrt(N-v),r[dep+1]-1);i>=dep;i--){// 枚举当前层的高度// 高度下限：至少 dep// 高度上限：不能超过下一层高度-1，且受体积限制 (N-v)/(i*i)for(intj=min((N-v)/i/i,h[dep+1]-1);j>=dep;j--){r[dep]=i;h[dep]=j;intcur_s=s+2*i*j;// 加上当前层的侧面积if(dep==M)cur_s+=i*i;// 最底层额外加上下底面积dfs(dep-1,v+i*i*j,cur_s);}}}intmain(){cin>>N>>M;// 预处理前 i 层的最小体积和最小侧面积（假设半径 = 高 = i）for(inti=1;i<=M;i++){minv[i]=minv[i-1]+i*i*i;// 体积：i^3mins[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;return0;}

功能分析

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>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

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>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}