题目链接：https://www.dotcpp.com/oj/problem2353.html

    题目解析：给出蛋糕的总体积 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为待枚举的第一层高度）。
    下面给出搜索框架：

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

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

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

    如果不考虑剪枝，直接爆搜，会超时，所以加入两个剪枝操作。

    • 假设现在搜索到第 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）

    完整代码：

    1. import java.util.*;
    2. public class Test{
    3.     public static int n, m;
    4.     public static int ans = Integer.MAX_VALUE;
    5.     public static void dfs(int depth, int v, int s, int r, int h){
    6.         if(depth == m){
    7.             if(v == n){
    8.                 ans = s;
    9.             }
    10.             return;
    11.         }
    12.         if(v + (r-1)*(r-1)*(h-1)*(m-depth) < n){
    13.             return;
    14.         }
    15.         if(v + m - depth > n){
    16.             return;
    17.         }
    19.         for (int i = r -1 ; i >= m - depth; i--){
    20.             for (int j = h - 1; j >= m - depth; j--){
    21.                 if((i * i * j + v <= n) && (s + 2 * i * j < ans)){
    22.                     dfs(depth + 1, v + i * i * j, s + 2 * i * j, i ,j);
    23.                 }
    24.             }
    25.         }
    26.     }
    27.     public static void main(String[] args) {
    28.         Scanner sc = new Scanner(System.in);
    29.         n = sc.nextInt();
    30.         m = sc.nextInt();
    32.         for(int r = m; r * r * m <= n; r++){
    33.             for(int h = m; r * r * h <= n; h++){
    34.                 if(r * r + 2 * r * h < ans){
    35.                     dfs(1, r * r * h, r * r + 2 * r * h, r, h);
    36.                 }
    37.             }
    38.         }
    39.         System.out.println(ans);
    41.     }
    42. }