题意

• 给定蛋糕层数，蛋糕总体积，求解最最小表面积
• 对于蛋糕每层的半径和高度都是整数，且对于第i层，半径和高度都不小于i

思路

• 对于每一层，枚举可能的高度和半径，计算体积和表面积
• 对于枚举顺序，从最底下一层往上枚举，因为上面的层数越多，受限越多
• 对于每一层，半径和高度的下界都是层数，上界都是上一层的半径-1or高度-1
• 做到以上，通过20%，其余TLE

剪枝

• 如果枚举到一定层数，总体积-当前体积已经小于0，直接回溯
• 如果枚举到一定层数，累计表面积已经大于之前的最优解，直接回溯
• 如果枚举到一定层数，剩下的体积堆成一块都超过当前最优表面积，直接回溯

对第三条剪枝的论证

• 对于体积和表面积：,变为两倍，维持体积不变，高度缩小四倍，表面积缩小一半，所以体积不变的情况下，表面积最优是半径取最大，把所有的堆成一块即可。

AC代码

#include<bits/stdc++.h>
using namespace std;

int n,m,r[40],h[40];
int ans=1e9+7;
void dfs(int dp,int v,int s){
    if(v<0||s>ans||s+v/r[dp-1]*2>ans) return;
    if(dp>m){
        if(v==0) ans=min(s+r[1]*r[1],ans);
        return;
    }
    
    for(int i=r[dp-1]-1;i>=m-dp+1;i--){
        for(int j=h[dp-1]-1;j>=m-dp+1;j--){
            r[dp]=i;
            h[dp]=j;
            dfs(dp+1,v-i*i*j,s+j*i*2);
        }
    }
    
}
int main(){
    scanf("%d%d",&n,&m);
    r[0]=sqrt(n)+1;
    h[0]=n+1;
    dfs(1,n,0);
    printf("%d",ans);
    return 0;
}