acwing168. 生日蛋糕

题目

题解

参考题解转送们

剪枝

#include<iostream>
#include<cmath>
using namespace std;
const int N=25,inf=1e9;
int H[N],R[N];
int n,m,ans=inf;
int minv[N],mins[N];
void dfs(int u,int v,int s){
    if(v+minv[u]>n)return;//剪枝1：当前体积或者表面积>总体积或者当前最小表面积
    if(s+mins[u]>=ans)return;
    if(s+2*(n-v)/R[u+1]>=ans)return;//剪枝2：需要推导
    
    if(!u){
        if(v==n)ans=min(s,ans);//到达第0层体积为n则满足条件
        return;
    }
    //半径和高度都从最大值开始，最大值由下一层的半径和高度确定，n-v是剩余的体积，当高度为1时r取最大值，两者取最小值
    for(int r=min(R[u+1]-1,(int)sqrt(n-v));r>=u;r--){
        for(int h=min(H[u+1]-1,(n-v)/r/r);h>=u;h--){
            int t=0;
            if(u==m)t=r*r;//第一层的圆柱地面要加上
            R[u]=r,H[u]=h;
            dfs(u-1,v+r*r*h,s+2*r*h+t);
        }
    }
    
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        minv[i]=minv[i-1]+i*i*i;//第一层最小为1，第二层满足条件最小为2...
        mins[i]=mins[i-1]+2*i*i;
    }
    R[m+1]=inf,H[m+1]=inf;
    dfs(m,0,0);
    if(ans==inf)cout<<0<<endl;
    
    else cout<<ans<<endl;
    
    
    return 0;
}