B24 DFS剪枝 生日蛋糕

#include<bits/stdc++.h> //by:hansang 代码来源于y总 
using namespace std;
const int N=25, INF=1e9;
 
int n, m;
int minv[N], mins[N];
int R[N], H[N];
int ans;
 
void dfs(int x, int v, int s)
{
    if( v+minv[x]>n) return; //总体积加上现层数最小体积大于 n     return 
    if( s+mins[x]>=ans ) return; //总表面积加上现层数最小表面积大于 ans     return 
    if( s+2* (n-v)/R[x+1] >=ans) return; //剩余体积除以现最大半径乘 2加 s大于 ans      return 
                                         //  r*r*r /(max r) *2+s=(min 表面积) >ans(最优解) 
    if(x==0) //到底啦 
    {
        if(v==n) ans=s; //总体积等于n    ans=总表面积 
        return;
    }
 
    for(int r= min( R[x+1]-1, (int)sqrt(n-v) ); r>=x; r--) 
    //rmax=自己下面的半径-1(因为是严格大于)或剩余体积开根号(h取1)  rmin=现层数 
    {
        for(int h= min( H[x+1]-1, (n-v)/r/r ); h>=x; h--) 
        //hmax=自己下面的高-1或剩余体积/r/r(v=h*r*r)   hmin=现层数 
        {
            int t=0;
            if(x==m) t=r*r; //最底下一层的蛋糕圆盘面积(从上往下看就看到底盘) 
            R[x]=r; H[x]=h; //记录,方便下次取极限 
            dfs(x-1, v+r*r*h, s+2*r*h+t); 
        }
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        minv[i]=minv[i-1] + i*i*i; //体积最小是取 h=i ,r=i  h*r*r 
        mins[i]=mins[i-1] + 2*i*i; //表面积最小是取 h=i,r=i  2*r*r 
    }
    R[m+1]=H[m+1]=INF; //初始化 
    
    ans=INF;
    dfs(m, 0, 0); //从最底下开始递归,初始总体积和总表面积都是零 
    if(ans==INF) ans=0; //无解 
    printf("%d\n", ans);
    return 0;
}