|
|
## [$AcWing$ $168$. 生日蛋糕](https://www.acwing.com/problem/content/170/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
$7$月$17$日是 $Mr.W$ 的生日,$ACM-THU$ 为此要制作一个体积为 $Nπ$ 的 $M$ 层生日蛋糕,每层都是一个圆柱体。
|
|
|
|
|
|
设 **从下往上数** 第 $i$ 层蛋糕是半径为 $R_i$,高度为 $H_i$ 的圆柱。
|
|
|
|
|
|
当 $i<M$ 时,要求 $R_i>R_{i+1}$ 且 $H_i>H_{i+1}$。
|
|
|
|
|
|
由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积 $Q$ 最小。
|
|
|
|
|
|
令 $Q=Sπ$ ,请编程对给出的 $N$ 和 $M$,找出蛋糕的制作方案(适当的 $R_i$ 和 $H_i$ 的值),使 $S$ 最小。
|
|
|
|
|
|
除 $Q$ 外,以上所有数据皆为 **正整数**。
|
|
|
|
|
|
<center><img src='https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3Uub3JnL3VwbG9hZC9waWMvNTI0LnBuZw?x-oss-process=image/format,png'></center>
|
|
|
|
|
|
**输入格式**
|
|
|
输入包含两行,第一行为整数 $N$,表示待制作的蛋糕的体积为 $Nπ$。
|
|
|
|
|
|
第二行为整数 $M$,表示蛋糕的层数为 $M$。
|
|
|
|
|
|
**输出格式**
|
|
|
输出仅一行,是一个正整数 $S$(若无解则 $S=0$)。
|
|
|
|
|
|
**数据范围**
|
|
|
$1≤N≤10000,1≤M≤20$
|
|
|
|
|
|
**输入样例**:
|
|
|
```cpp {.line-numbers}
|
|
|
100
|
|
|
2
|
|
|
```
|
|
|
|
|
|
**输出样例**:
|
|
|
```cpp {.line-numbers}
|
|
|
68
|
|
|
```
|
|
|
|
|
|
### 二、题目分析
|
|
|
|
|
|

|
|
|
|
|
|
#### 1、梳理题意
|
|
|
>将 **自上而下** 的各层蛋糕编号为$1 \sim m$,题目要求我们设计一个 $m$ 层蛋糕,**下层** 的蛋糕比 **上层** 的蛋糕 **半径** 和 **高度** 都 **要大** ,并且总的体积为$n$,求 **最小的表面积**。
|
|
|
|
|
|
#### 2、公式推导
|
|
|
##### 体积
|
|
|
$$\large V_{全}=\sum_{i=1}^{m} \pi R_i ^2 H_i$$
|
|
|
|
|
|
|
|
|
##### 上表面积$S_上$
|
|
|
* 第$m$层的上表面积是$S_m - S_{m-1}$
|
|
|
* 第$m-1$层的上表面积是$S_{m-1} - S_{m-2}$
|
|
|
* ...
|
|
|
* 第$2$层的表面积是$S_2-S_1$
|
|
|
* 第$1$层的上表面积是$S_1$
|
|
|
$$\large \therefore S_{上}=S_m-S_{m-1}+S_{m-1}-S_{m-2}+...+S_2-S_1+S_1=S_m=\pi R_m^2$$
|
|
|
|
|
|
>**解释**:被盖上的那部分面积,都会由上面的小蛋糕补上
|
|
|
|
|
|
##### 侧表面积$S_侧$
|
|
|
**侧表面积** 就是每个圆柱的侧边面积,也就是一个围成圆柱的矩形面积,**圆的边长** 乘以 **高度** :
|
|
|
|
|
|
$$\large S_侧=\sum_{i=1}^m 2 \pi R_i H_i$$
|
|
|
|
|
|
##### 整体表面积$S_整$
|
|
|
上表面积 + 侧表面积:
|
|
|
$$\large S_{整}=S_{上}+S_{侧}=\pi R_m^2 +\sum_{i=1}^{m}2 \pi R_i H_i $$
|
|
|
|
|
|
|
|
|
#### 3、剪枝与优化技巧
|
|
|
|
|
|
##### (1) 优化搜索顺序
|
|
|
为了 **先搜索的分支数少**,应该 **自大到小** 搜索:
|
|
|
* **从第$m$层搜索到第$1$层**
|
|
|
* 体积公式中$R_i$是 **平方级别** ,**变化率要高于**$H_i$,先搜$R_i$,再搜$H_i$
|
|
|
> **解释**:类比 **[运输小猫](https://www.acwing.com/problem/content/167/)**,大头在前,可以使$dfs$搜索树搜索的层数减少,搜索效率提升
|
|
|
|
|
|
##### (2) 各层高度和半径的范围
|
|
|
> 设第$i$层蛋糕的半径是$R_i$,高度是$H_i$,因为 **半径** 和 **高度** 都是 **整数**,并且$R_i < R_{i+1},H_i < H_{i+1}$
|
|
|
> 由于 **最上层** 的蛋糕半径和高度也必须是 **正整数**,所以$R_1$和$H_1$至少是$1$,$R_2$要大于$R_1$,至少是$2$,由此可见:第$i$层蛋糕的 **半径** 和 **高度** 至少是$i$
|
|
|
第$i$层的 **高度** 和 **半径** **至少** 是$i$,这就是 **各层高度和半径的最小值**, 这是$R_i,H_i$的 **下界**
|
|
|
$R_i < R_{i+1},H_i < H_{i+1}$,这是一个**上界**
|
|
|
|
|
|
###### (3) 预处理
|
|
|
>为了在走一半时,能迅速 **估计** 继续走下去是否能成功,我们可以提前预处理出两个数组:
|
|
|
> - $mins[i]$ : **$1$到$i$层侧表面积的最小值**:
|
|
|
$$\large mins[i] = mins[i-1] + 2* i * i$$
|
|
|
**解释**:我们手中资源是剩余的体积,随时需要知道剩余$1\sim i$这些层中,我们至少需要多少体积,及时发现不合理的分支并及时停止。
|
|
|
> - $minv[i]$ : **$1$到$i$层体积的最小值**:
|
|
|
$$\large minv[i] = minv[i-1] + i * i * i$$
|
|
|
> **解释**:从第$m$层搜到第$u$层总的体积是$v$,而从第$1$层到第$u$层体积至少是$minv[u]$,所以当$v + minv[u] > n$时就说明 **肯定后续会超过体积**$n$,**方案不合法** (**可行性剪枝**)
|
|
|
|
|
|
##### (4) **找出两个变量之间的制约关系**
|
|
|
从第$m$层蛋糕搜到当前的第$u$层时,设已经使用的表面积是$s$,体积是$v$,则从第$u$层到第$1$层留给我们的体积 **最多** 只有$n - v$,所以第$u$层的半径$$\large \pi R_u^2H_u <= n - v$$
|
|
|
|
|
|
题目很贴心,不想让我们计算$\pi=3.1415926...$这样的小数,而是让我们计算去掉$\pi$后的常数系数,下面的论述中将忽略掉$\pi$:
|
|
|
|
|
|
$$\large R_u <= \sqrt{((n-v)/H_u)}$$
|
|
|
|
|
|
$H_u$的 **最小值** 是$u$,取$u$时,右侧相当于取到了 **最大值**,不等式也依然成立,所以
|
|
|
|
|
|
$$
|
|
|
\large \left\{\begin{array}{ll}
|
|
|
R_u <= \sqrt{(n-v)/u} & \\
|
|
|
H_u <= (n-v) / R_u^2 &
|
|
|
\end{array}\right.
|
|
|
$$
|
|
|
|
|
|
> **解释**: $R_u$不是随便想多少就是多少的,受到给定后续大小$n-v$和当前层次$u$的限制,不能大于$\sqrt{(n-v)/u}$。而另一个变量$H_u$也不随便想多少就是多少的,它的受限和$R_u$相关,一旦确定了$R_u$的值,$H_u$的 **上限** 也就确定了。
|
|
|
这就是$H_u$和$R_u$的 **另一个上界**,两个变量$R_i$与$H_i$不是孤立的,而是存在制约关系,我们在上面推导的过程,其实就是试图找出两者之间的关联制约关系,这样就可以在$dfs$过程中,及时找到冲突点,及时止损,`return false`。
|
|
|
|
|
|
既然$R_i$和$H_i$都同时要受两个条件的约束,那么 **他们的上界取需要取 两个上界条件 的最小值**
|
|
|
|
|
|
|
|
|
##### (5) 深搜函数设计
|
|
|
|
|
|
参数设计:
|
|
|
* **$u$:当前是第几层**
|
|
|
* **$v$:已经占用的空间**
|
|
|
* **$S$:已经获得的表面积**
|
|
|
|
|
|
令
|
|
|
① $ans$是 **之前搜到的最小表面积**
|
|
|
② $S$ **=$m$层的上表面积+已完成的各层侧表面积和**
|
|
|
|
|
|
##### (6) 剪枝策略
|
|
|
* **搜索到一半时表面积已超过了目前的最优解**
|
|
|
如果$s + mins[u] >= ans$,也就是**当这个方案搜下去的表面积不可能优于小于之前搜到的解**时,应该否定这个方案
|
|
|
|
|
|
* **表面积和体积之间的制约关系**
|
|
|
从第$1$层到第$u$层的 **侧表面积**
|
|
|
$$S_{1 \sim u}=\sum_{i=1}^{u}2 \pi R_iH_i$$
|
|
|
|
|
|
第$1$层到第$u$层的体积($V_u$是指 **从$m$层出发** **到达$u$层** 时,已使用了的体积)
|
|
|
$$V_{1\sim u}=n-V_u=\sum_{i=1}^{u}\pi R_i^2Hi$$
|
|
|
|
|
|
为了找出两者之间的关系,需要构造成同样的部分:**侧表面积** 那个$R_iH_i$,体积这个$R_i^2H_i$,很明显,表面积乘上一个$R_i$再除一个$R_i$就能得到一个和体积相关的东西,但$R_i$目前是不确定的(正在尝试中),我们需要依赖的是前面$u+1$的$R_{u+1}$(本分枝中,前面$u+1$层的$R_{u+1}$已经设定),所以就乘上再除上$R_{u+1}$试试:
|
|
|
$$S_{1 \sim u}=\sum_{i=1}^{u}2 \pi R_iH_i=\frac{2\pi}{R_{u+1}}\sum_{i=1}^{u}R_{u+1}R_iH_i$$
|
|
|
同时因为$R_{u+1}>R_i$,所以:
|
|
|
$$S_{1 \sim u} > \frac{2}{R_{u+1}}\sum_{i=1}^{u} \pi R_i^2Hi$$
|
|
|
|
|
|
将 **体积等式** 代入:
|
|
|
$$S_{1 \sim u} > \frac{2 (n-V_u)}{R_{u+1}}$$
|
|
|
|
|
|
因此如果$$\large S_总=S_已+S_{1 \sim u}>=S_{ans}$$
|
|
|
就是说当前阶段,后面不管怎么整,都肯定不会比目前的最优答案$S_{ans}$更牛$X$,可以剪枝
|
|
|
|
|
|
即当
|
|
|
|
|
|
$$S_已+\frac{2(n−V)}{R_{u+1}}>=S_{ans}$$
|
|
|
|
|
|
时就可以剪枝掉(**最优性剪枝**)
|
|
|
|
|
|
|
|
|
##### (7) 递归出口
|
|
|
- 最后递归的边界是$u == 0$,遍历完了所有层蛋糕
|
|
|
- 当$v$恰好是$n$时,就可以更新最优解了
|
|
|
|
|
|
### 四、实现代码
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
const int N = 22;
|
|
|
int n; // 待制作的蛋糕的体积为
|
|
|
int m; // 蛋糕的层数为 m
|
|
|
int ans = INF; // 最小表面积,预求最小,先设最大
|
|
|
int mins[N]; // 每一层的最小表面积
|
|
|
int minv[N]; // 每一层的最小体积
|
|
|
int R[N], H[N]; // 为每一层蛋糕分配的半径和高度
|
|
|
|
|
|
// u:正在研究第几层
|
|
|
// v:已经使用了的体积
|
|
|
// s:已经使用了的表面积
|
|
|
void dfs(int u, int v, int s) {
|
|
|
// 如果来到第u层,发现,已经使用过的体积v,加上第1~u层最小体积minv[u] ,大于整体的体积n,就不用再继续了
|
|
|
if (v + minv[u] > n) return;
|
|
|
|
|
|
// 如果来到第u层,发现,已经使用过的表面各s,加上第u层及以上所有层需要的表面积mins[u]
|
|
|
// 大于当前最优解了,就不用再继续研究了,还不如最优解,再研究也是白扯
|
|
|
if (s + mins[u] >= ans) return;
|
|
|
|
|
|
// 第二个最优性剪枝,侧面积和体积不是孤立存在的,是有关联关系的。
|
|
|
// 不符合这个关联关系的Ri和Hi是没有必要继续的
|
|
|
if (2 * (n - v) / R[u + 1] + s >= ans) return;
|
|
|
|
|
|
// 摆完所有层蛋糕
|
|
|
if (u == 0) {
|
|
|
// 如果已经使用的体积等于n,如果是,那么更新答案
|
|
|
if (v == n) ans = s;
|
|
|
return;
|
|
|
}
|
|
|
// 枚举每一个可能的半径,同理,半径由大到小
|
|
|
for (int r = min(R[u + 1] - 1, (int)sqrt((n - v) / u)); r >= u; r--)
|
|
|
for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--) {
|
|
|
// 如果是第m层,需要加上一个底面积,其它层就只计算侧面积
|
|
|
int t = (u == m ? r * r : 0);
|
|
|
// 记录下第u层的选择,半径:r,高度:h
|
|
|
R[u] = r, H[u] = h; // 因为静态数组可以重复按索引写入,所以不需要回溯
|
|
|
// 递归上一层,体积变为v+r*r*h,表面积由s变大为 s + 2 * r * h + t
|
|
|
dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
|
|
|
}
|
|
|
}
|
|
|
int main() {
|
|
|
cin >> n >> m;
|
|
|
// 预处理
|
|
|
for (int i = 1; i <= m; i++) {
|
|
|
// 第i层,半径最小是i,高度最小是i,否则更小层无法获得整数解
|
|
|
// 预处理出每层及上边所有层的最小表面积,看清楚这是一个叠加的关系,不是简单的计算,是递推式
|
|
|
mins[i] = mins[i - 1] + 2 * i * i;
|
|
|
// 预处理出每层及上边所有层的最小体积
|
|
|
minv[i] = minv[i - 1] + i * i * i;
|
|
|
}
|
|
|
// 初始化为无穷大,防止在计算下层半径高度时取到0
|
|
|
R[m + 1] = H[m + 1] = INF;
|
|
|
|
|
|
// 从下向上进行深搜,按经验来看,这样能减少出发时的分枝数量,效率提升
|
|
|
// 从m层出发,此时的体积为0,此时的表面积为0
|
|
|
dfs(m, 0, 0);
|
|
|
|
|
|
// 输出答案
|
|
|
if (ans == INF)
|
|
|
puts("0");
|
|
|
else
|
|
|
printf("%d\n", ans);
|
|
|
return 0;
|
|
|
}
|
|
|
``` |