python

11 KiB

Raw Permalink Blame History Unescape Escape

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`. 生日蛋糕

一、题目描述

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 外，以上所有数据皆为 正整数。

输入格式 输入包含两行，第一行为整数 N，表示待制作的蛋糕的体积为 Nπ。

第二行为整数 M，表示蛋糕的层数为 M。

输出格式 输出仅一行，是一个正整数 S（若无解则 S=0）。

数据范围 1≤N≤10000,1≤M≤20

输入样例：

100
2

输出样例：

二、题目分析

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

解释：类比 运输小猫，大头在前，可以使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时，就可以更新最优解了

四、实现代码

#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;
}

11 KiB Raw Permalink Blame History Unescape Escape

AcWing 168. 生日蛋糕