AcWing 168. 生日蛋糕

题目传送门

一、题目分析

本题虽然看起来比较复杂，但是只要稍加分析，思路还是很清晰的。(以我现在的实力来看，这题简直就是BT,如果没做过，直接在考场考这题，考十次挂十次，无一例外。)

将自上而下的各层蛋糕编号为\(1-m\)，题目要求我们设计一个\(m\)层蛋糕，下层的蛋糕比上层的蛋糕半径和高度都要大，并且总的体积为\(n\)，求最小的表面积。

设第\(i\)层蛋糕的半径是\(R_i\)，高度是\(H_i\)，半径和高度都是整数。有\(R_i < R_{i+1},H_i < H_{i+1}\)，根据题目要求，我们下面先忽略体积和表面积公式中的\(π\)。(出题人为了让我们不用考虑π,先是让\(n=Nπ\),又友好的把表面积\(Q=Sπ\),不让我们再关心π,良心！)

由于最上层的蛋糕半径和高度都要是正整数，所以\(R_1\)和\(H_1\)至少是\(1\)，\(R_2\)要大于\(R_1\)，至少是\(2\)，由此可得，第\(i\)层蛋糕的半径和高度至少是\(i\)。

蛋糕体积公式: $$V_总=\sum_{i=1}^{m} R_i ^2 H_i$$

表面积公式为:$$S_总= R_m^2 + \sum_{i=1}^{m}2R_i*H_i$$

也就是最下层蛋糕的底面积加上各层蛋糕的侧面积，这里有个简单的推导:第\(m\)层的上表面积是\(S_m - S_{m-1}\)，第\(m-1\)层的上表面积是\(S_{m-1} - S_{m-2}，...\)，第\(1\)层的上表面积是\(S_1\)，加起来得到上表面积的总和就是\(S_m = R_m^2\)。

二、剪枝优化

优化搜索顺序
为了先搜索的分支数少，我们应该自大到小搜索，也就是从第\(m\)层搜索到第\(1\)层，并且体积公式中\(R_i\)是平方级别的，变化率要高于\(H_i\)，所以先搜\(R_i\)，再搜\(H_i\)。

下面考虑各层高度和半径的范围，前面说到，第\(i\)层的高度和半径至少是\(i\)，这就是各层高度和半径的最小值，并且\(R_i < R_{i+1}，H_i < H_{i+1}\)，这是其中的一个上界。

设\(mins[i]\)表示\(1\)到\(i\)层表面积的最小值，\(minv[i]\)表示\(1\)到\(i\)层体积的最小值，则$$mins[i] = mins[i-1] + 2* i * i$$
因为第\(i\)层高度和半径都至少是\(i\),

\[minv[i] = minv[i-1] + i * i * i \]

我们从第\(m\)层蛋糕搜到当前的第\(u\)层时，设已经使用的表面积是\(s\)，体积是\(v\)，则从第\(u\)层到第\(1\)层留给我们的体积最多只有\(n - v\)了，所以第\(u\)层的半径\(R_u*R_u*H_u <= n - v\)，则：\(R_u <= sqrt((n-v)/H_u)\)，\(H_u\)至少是\(u\)，取最小值时，不等式当然也成立，所以\(R_u <= sqrt((n-v)/u)\)。

当然，算法竞赛进阶指南上面的公式这里没有除以\(u\)，因为把\(H\)看作最小是\(1\)了，对结果影响不大。

同样，\(H_u <= (n-v) / R_u / R_u\)，这就是\(H_u\)和\(R_u\)的另一个上界，上界取两个上界的最小值即可。

可行性剪枝：前面说到从第\(m\)层搜到第\(u\)层总的体积是\(v\)，而从第\(1\)层到第\(u\)层体积至少是\(minv[u]\)，所以当\(v + minv[u] > n\)时就说明超过了给定的体积\(n\)，方案不合法。

最优性剪枝：

• 第一个最优性剪枝:搜索到一半时表面积已超过了目前的最优解
  \(s + mins[u] >= ans\)时，这里\(ans\)是之前搜到的最小表面积，也就是当这个方案搜下去的表面积不可能优于小于之前搜到的解时，就应该否定这个方案。

• 第二个最优性剪枝:推表面积公式和体积公式的关系
  从第\(1\)层到第\(u\)层的表面积（不考虑\(π\)）

\[S_{1 \sim u}=\sum_{i=1}^{u}2R_iH_i \]

第\(1\)层到第\(u\)层的体积,(\(V_u\)是指到达\(u\)层时，已使用了的体积)

\[n-V_u=\sum_{i=1}^{u}R_i^2Hi \]

我们为了找出两者之间的关系，需要构造成同样的部分:表面积那个\(R_iH_i\),体积这个\(R_i^2H_i\)，很明显，表面积乘上一个\(R_i\)再除一个\(R_i\)就能得到一个和体积相关的东西，但\(R_i\)目前是不确定的，我们需要依赖的是前面\(u+1\)的\(R_{u+1}\),所以就乘上再除上\(R_{u+1}\)试试：

\[S_{1 \sim u}=\sum_{i=1}^{u}2R_iH_i=\frac{2}{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}R_i^2Hi \]

所以惊奇地发现

\[S_{1 \sim u} > \frac{2(n-V)}{R_{u+1}} \]

因此\(S_总=S+S_{1 \sim u}>=S_{ans}\) ，即
\(S+\frac{2(n?V)}{R_{u+1}}>=S_{ans}\)时就可以剪枝掉（最优性剪枝)

最后递归的边界是\(u == 0\)，遍历完了所有层蛋糕，当\(v\)恰好是\(n\)时，就可以更新最优解了。

三、实现代码

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 22;
int n;         //表示待制作的蛋糕的体积为 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,加上第u层及以上所有层需要的体积minv[u] ,大于整体的体积n，就不用再继续了
    if (v + minv[u] > n) return;

    //如果来到第u层，发现，已经使用过的表面各s,加上第u层及以上所有层需要的表面积mins[u]
    //大于当前最优解了，就不用再继续研究了，还不如最优解，再研究也是白扯
    if (s + mins[u] >= ans) return;

    //还有第二个最优性剪枝
    if (2 * (n - v) / R[u + 1] + s >= ans) return;

    //如果摆完了第一层，来到了第0节
    if (!u) {
        //如果已经使用的体积等于n，如果是，那么记录答案
        if (v == n) ans = min(ans, s);
        return;
    }
    //枚举每一个可能的半径,同理，半径由大到小
    // r起始：在下面一层的半径-1做为最小值
    // r起始：Ru?Ru?Hu<=n?v 则Ru<=sqrt((n?v)/Hu)，Hu至少是u，取最小值是，不等式当然也成立，所以Ru<=sqrt((n?v)/u)。
    // 两个都可以做为起始值，那么，哪个小就用哪个
    // r终止：r是必须大于层号的，否则小的层没法放整数，所以r>=u
    for (int r = min(R[u + 1] - 1, (int)sqrt((n - v) / u)); r >= u; r--)
        // for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r--)
        //枚举每一个可能的高度，同理，高度由大到小
        //  h起始：在下面一层的高度-1做为最小值
        //  h起始：Ru?Ru?Hu<=n?v --> Hu<=(n?v)/Ru/Ru 即Hu<=(n-v)/r/r
        //  两个都可以做为起始值，那么，哪个小就用哪个
        //  h终止：h是必须大于层号的，否则小的层无法放整数，所以h>=u
        for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h--) {
            //如果是最后第m层，那么是Rm*Rm,否则就是0
            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)
        cout << "0" << endl;
    else
        cout << ans << endl;
    return 0;
}

四、写给复习时的自己

这道题是看懂了，但是，没有题解，没有代码，根本重新写不出来的。复习时，一定要想清楚表面积和体积的关联关系，如何确定它们之间的不等式关系，研究清楚各种常见的剪枝方案都有啥，而不是看懂题解，看懂代码就完事，路，还有很长很长，加油。