信息学奥赛一本通T1441-生日蛋糕（JAVA+详细分析）

题目解析：给出蛋糕的总体积 n 和蛋糕层数 m，求最佳的各层蛋糕的半径和高度分配方案，使得蛋糕表面积最小。

题目条件理解：对各层蛋糕进行编号，自下而上，最底层编号为1，最高一层编码为m。对于半径和高度存在约束，Ri > Ri+1 和 Hi > Hi+1。
蛋糕表面积的相关计算：
第1层~第m层顶端表面积（即圆柱体上表面）等价于 第1层的底面面积
总表面积 = 第1层的底面面积 + sum（第1层~第m层的侧面积）

问题求解：
这是一道搜索类型的题目，常规做法是从第一层蛋糕开始，逐层向上搜索，直至搜索到最优解。
但是第一层蛋糕的半径和高度没有明确给出上下限，需要我们自己推导。
由于第i+1层蛋糕的半径和高度 必须大于 第i层蛋糕的半径和高度，由此可推导出第1层蛋糕半径的下限为m。（注：极端情况下，第一层的半径为1，第二层的半径为2，…，第m层的半径为m）
同理，第1层的高度的下限为m。
那第一层的半径上限如何确定呢？这个需要借助已经给出的蛋糕总体积n，我们的想法是从第一层开始逐层枚举，那么第2层~第m层同样是会占据一部分体积，那么要求第一层在分配的时候，不能把体积都分配完，所以由此推出第一层蛋糕半径的上限：r * r * m <= n（注：r为待枚举的第一层半径高度）。
同理，第1层的高度的上限：r * r * h <= n（注：h为待枚举的第一层高度）。
下面给出搜索框架：

for(int r = m; r * r * m <= n; r++){
    for(int h = m; r * r * h <= n; h++){
        if(r * r + 2 * r * h < ans){//只有有机会搜索到更优的解进行递归
            //确定第一层蛋糕的半径和高度，逐层往上搜索
            //dfs()细节待补充
            dfs();
        }
    }
}

接下来谈谈如果逐层搜索以及如何剪枝。

public static void dfs(int depth, int v, int s, int r, int h){
    //暂时不考虑剪枝的细节
    //由于第i+1层的高度和半径 < 第i层的高度和半径
    //故第i+1层的高度和半径的下限分别为r-1;(此处r为第i层的半径, h为第i层的高度)
    //由于必须保证第m层的最小半径和高度为1,所以借此确定第i+1层的半径和高度的上限
    //并且需要判断当前选取的半径i和高度j不能超过总体积和小于最优解，才可再往上一层搜索
    for (int i = r -1 ; i >= m - depth; i--){
        for (int j = h - 1; j >= m - depth; j--){
            if((i * i * j + v <= n) && (s + 2 * i * j < ans)){
                dfs(depth + 1, v + i * i * j, s + 2 * i * j, i ,j);
            }
        }
    }
}

如果不考虑剪枝，直接爆搜，会超时，所以加入两个剪枝操作。
● 假设现在搜索到第 depth 层，接下来的 M - depth层的高度和半径均取最大值 h-1 和 r-1，仍然小于总体积n，则剪枝，代码为：v + (r-1)*(r-1)*(h-1)*(m-depth) < n。（注：v为搜索到第 depth 层累计的体积，r 和 h 为 第 depth层所确定的半径和高度）
● 假设现在搜索到第 depth 层，接下来的 M - depth层的高度和半径均取最小值1，仍然大于总体积n，则剪枝，代码为：v + m - depth > n。（注：v为搜索到第 depth 层累计的体积，r 和 h 为 第 depth层所确定的半径和高度，在代码处做了化简，原始代码：v + 1 * 1 * 1 *m - depth > n）

完整代码：

import java.util.*;
public class Test{
    public static int n, m;
    public static int ans = Integer.MAX_VALUE;
    public static void dfs(int depth, int v, int s, int r, int h){
        if(depth == m){
            if(v == n){
                ans = s;
            }
            return;
        }
        if(v + (r-1)*(r-1)*(h-1)*(m-depth) < n){
            return;
        }
        if(v + m - depth > n){
            return;
        }
        for (int i = r -1 ; i >= m - depth; i--){
            for (int j = h - 1; j >= m - depth; j--){
                if((i * i * j + v <= n) && (s + 2 * i * j < ans)){
                    dfs(depth + 1, v + i * i * j, s + 2 * i * j, i ,j);
                }
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int r = m; r * r * m <= n; r++){
            for(int h = m; r * r * h <= n; h++){
                if(r * r + 2 * r * h < ans){
                    dfs(1, r * r * h, r * r + 2 * r * h, r, h);
                }
            }
        }
        System.out.println(ans);
    }
}

参考资料：https://blog.csdn.net/qq_42367531/article/details/85055165?utm_term=%E4%B8%80%E6%9C%AC%E9%80%9A1674%E5%A0%86%E8%9B%8B%E7%B3%95&utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~sobaiduweb~default-0-85055165&spm=3001.4430