本文全文忽略式中的 $\pi$，以保证总是用整数运算。
题意简述
一个 $M$ 层蛋糕的体积为 $N$。
第 $i$ 层蛋糕的半径为 $R_i$， 高度为 $H_i$。并且从下往上一层比一层小，一层比一层薄。
我们要在蛋糕体积为 $N$ 时，使蛋糕外表面积 $S$ 最小。无解输出 $0$。
分析
一个蛋糕有 $M$ 层，我们从上往下编号，最上面的一层叫第 $1$ 层，最下面一层叫第 $M$ 层。
圆柱的体积为 $\pi r^2 h$，所以需满足的条件可写为
$$ R_1^2 H_1 + R_2^2 H_2 + \dots R_M^2 H_M = N. $$
整个蛋糕的外表面等于侧面积加上表面。
我们知道圆柱侧面积为 $2\pi rh$，圆柱底面积为 $\pi r^2$，所以第 $i$ 层的侧面积为 $2\pi R_i H_i$，整个蛋糕的上表面为第 $M$ 层的底面。所以我们需要求最小的
$$ S = 2(R_1 H_1 + R_2 H_2 + \dots + R_M + H_M) + R_M^2. $$
接着就开始写代码。先写框架和输入：
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
int main()
{
scanf("%d%d", &n, &m);
return 0;
}
然后写 DFS，有三个参数 $\mathit{dep}, v, s$，分别表示层数、已经用过的体积和已经用过的表面积。由于我们是从下往上枚举，所以传参的时候 $\mathit{dep}$ 传 $M$。
int n, m;
void dfs(int dep, int v, int s)
{
}
int main()
{
scanf("%d%d", &n, &m);
dfs(m, 0, 0);
return 0;
}接着写一下递归出口，如果层数小于 $1$，那就是走完了，看一看是不是符合条件（$v == N$），如果符合的话就打擂台，记录答案，最后跳出。
int n, m, ans = 2147483647;
void dfs(int dep, int v, int s)
{
if (dep == 0)
{
if (v == n)
ans = min(ans, s);
return ;
}
}也可以写出输出：
printf("%d\n", ans == 2147483647 ? 0 : ans);
即无解输出 $0$，有解输出解。
接下来进行第一个优化：搜索顺序。
枚举蛋糕大小要枚举 $r, h$，因为体积等于 $r^2 h$，所以先枚举 $r$，再枚举 $h$。
然后进行第二个优化：上下边界。
由于 $v$ 是已经使用过的体积，那剩余体积就是 $N - v = r^2 h$。
$r$ 的上限就是 $\min\left(\dfrac{\sqrt{N - v}}{h}, R_{\mathit{dep} + 1}- 1\right)$。并且注意，不能太大，不能大于等于上一层。此处的 $h$ 也可以替换成 $\mathit{dep}$。
那 $r$ 的下限就是 $\mathit{dep}$。每一层相差 $1$，最小就是层数。
$h$ 的上限为 $\min\left(\dfrac{N - v}{r^2}, H_{\mathit{dep} + 1} - 1\right)$，下限同理也是 $\mathit{dep}$。
由于需要取上一层的值，所以还需要设初始值。
每一次枚举时，更新 $R, H$ 数组。
最后递归下去，层数改变为上一层，体积加上这一层的体积，表面积加上这一层的侧面积，如果层数为 $M$，则还需要加上底面积。
经过这两个优化，可以写出代码（出口后）：
#include <cmath>
// 全局定义
int R[20], H[20];
// DFS
for (int r = min((int)sqrt((n - v) / dep), R[dep + 1] - 1); r >= dep; r--)
{
for (int h = min((n - v) / r / r, H[dep + 1] - 1); h >= dep; h--)
{
R[dep] = r, H[dep] = h;
dfs(dep - 1, v + r * r * h, s + 2 * r * h + (dep == m ? r * r : 0));
}
}
// 主函数
R[m + 1] = H[m + 1] = 2147483647;
接下来引入第三个优化：最优性剪枝。
原理很简单，如果面积已经超过之前的最小值，那根本不用想了，直接退出。写出代码（出口前，优化 1、2 后）：
if (s >= ans)
return ;
继续进行第四个优化：可行性剪枝。
这是需要两个新的前缀和数组：$\mathit{minv}, \mathit{mins}$。这里记录的分别是 $v, s$ 的最小值。
这个优化的策略是：
- 当前已用体积 + $\mathit{minv}_\mathit{dep}$ 不能超过 $n$；
- 当前已用面积 + $\mathit{mins}_\mathit{dep}$ 不能超过 $\mathit{ans}$。
前缀和数组都需要初始化。初始化时运算需要 $r, h$，$r, h$ 的最小值是 $\mathit{dep}$，所以得出主函数初始化代码（$R, H$ 初始化后，DFS 调用前）：
for (int i = 1; i <= m; i++)
{
minv[i] = minv[i - 1] + i * i * i;
mins[i] = mins[i - 1] + 2 * i * i;
}
而 DFS 中代码为（优化 3 后，优化 1、2 前）：
if (v + minv[dep] > n)
return ;
if (s + mins[dep] >= ans)
return ;
最后引入第五个优化：可行性剪枝。
这个的策略为：当前已用面积 + 这一层最小面积（满足总体积是 $v$）$\ge \mathit{ans}$。
$\mathit{dep}$ 层最少提供体积 $> \dfrac{n - v}{dep}$，则 $r^2 h = \dfrac{n - v}{dep}$。
表面积就为 $(n - v) \div \mathit{dep} \div (R_{\mathit{dep} + 1} - 1) \times 2$。
所以得代码（优化 4 后，优化 1、2 前）：
if (s + (n - v) / dep / (R[dep + 1] - 1) * 2 >= ans)
return ;
完整代码
|
|
Last modified on 2024-01-13