DFS(想都不想肯定要剪枝)

递归结束条件：

  1. 当层数 pp 达到 mm 层时
  2. 当体积已经超过 nn 时或得到的表面积比之前的最优值小时，更新 ansans

这道题以下几个剪枝：

  1. 当此时体积加上预处理的最大体积大于 nn 时，returnreturn
  2. 当前表面积加上最优表面积大于 ansans 时，returnreturn

code:

#include<stdio.h>
int min(int a,int b)
{
    if(a<b)
        return a;
    return b;
}
int a[101],b[101],n,m,ans=0x3f3f3f3f;//a存储表面积,b存储体积
void dfs(int v,int s,int p,int r,int h)//v为已用体积，s为已有表面积，p为剩余层数，r为半径，h为高
{
    int i,j,minn;
    if(p==0)//蛋糕已完成
    {
        if(v==n&&s<ans)//判断是否符合要求并得到更优解
            ans=s;//更新最优解
        return ;
    }
    if(v+b[p-1]>n)//体积超出
        return ;
    if(2*(n-v)/r+s>=ans)//重点：当前的表面积+余下的侧面积>当前最优值
    //侧面积S=2rh,体积V=r^2h,得到S=2V/r,注意，pai全被约掉
        return ;
    for(i=r-1;i>=p;i--)//枚举上一层的半径
    {
        if(p==m)
            s=i*i;
        minn=min((n-v-b[p-1])/(i*i),h-1);
        for(j=minn;j>=p;j--)//枚举上一层的高
            dfs(v+i*i*j,s+2*i*j,p-1,i,j);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<21;i++)
        b[i]=b[i-1]+i*i*i;//第i层使用的最大体积
    dfs(0,0,m,n+1,n+1);
    if(ans==0x3f3f3f3f)
        printf("0");
    else
        printf("%d",ans);
    return 0;
}