You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

230 lines
11 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

## [$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
```
### 二、题目分析
![](https://img2022.cnblogs.com/blog/8562/202203/8562-20220309161054889-1490078202.png)
#### 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(nV)}{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;
}
```