思路

搜索+剪枝

搜索时传入层数 $deep$，已用体积 $tov$ ,已用表面面积 $tov$ ，上一层的半径 $lr$ 以及 高度 $lh$ 。然后就可以开搜了。

• 剪枝1:如果接下来每一层都按照最小的来算，依然大于了总体积则可以剪去

• 剪枝2:如果接下来每一层都按照最小的来算，结果已经大于了求出的最优值，可以剪去

• 剪枝3:通过变形公式，如果接下来的体积用完所需的最小表面积已经大于了最优值，可以剪去

代码：

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,sv[21],sa[21],ans=2147483647;
void DFS(int deep,int tov,int tos,int lr,int lh)//从上往下第deep层,当前以用体积tov，以用表面积tos
                                                //上一层的半径lr,上一层的高度lh 
{
     if(deep==0)
     {
            if(tov==n)
              ans=min(ans,tos);
            return;
     }
     if(tov+sv[deep-1]>n)return;       
     if(tos+sa[deep-1]>ans)return;    
     if(tos+2*(n-tov)/lr>=ans)return; 
     for(int i=lr-1;i>=deep;--i)
     {
            if(deep==m)
               tos=i*i;
            int maxh=min(lh-1,(n-tov-sv[deep-1])/(i*i));  //当前高度所允许的最小值是上一层的高度减一和剩余体积
                                                         //与当前表面积的较小值 
            for(int h=maxh;h>=deep;--h)
               DFS(deep-1,tov+i*i*h,tos+2*i*h,i,h);
     }
}
int main()
{
    cin>>n>>m;
    memset(sv,0,sizeof(sv));
    memset(sa,0,sizeof(sa));
    for(int i=1;i<=m;++i)//提前预处理如果接下来i层都按照最小的计算所需的最表面积和体积 
    {
        sv[i]=sv[i-1]+i*i*i;
        sa[i]=sa[i]+i+i;
    }
    DFS(m,0,0,sqrt(n),n);
    if(ans!=2147483647)
       cout<<ans<<endl;
    else
       cout<<0<<endl;
    return 0;
    
}