题目链接
https://www.luogu.org/problemnew/show/P1731
解题思路
既然看不出什么特殊的算法，显然是搜索。。。
dfs(u,v,s,r0,h0)分别表示：
u为已经搜完的层数,v是现在的体积(不包括这一层),s是现在的表面积(所求的)(不包括这一层),r0是当前层的最大半径，h0是当前层的最大高度。
不加剪枝的dfs。。。(TLE!!!!)
本题的难点
剪枝
- 剪枝1：搜索到每一层时，如果当前的体积加上剩下层(包含当前层)的最小体积还是大于要求的总体积时，必须return，因为不论如何体积总不能符合要求。
- 剪枝2：搜索到每一层时，如果当前表面积加上剩下层(包含当前层)的最小表面积还是大于已经求出来的答案时，return，因为此答案一定不是最优解。
- 剪枝3：首先剪掉的是每一层的半径r和高h的范围。因为Ri>Ri+1且Hi>Hi+1，也就是说，较上层的半径和高一定比下层的小，所以很显然，每一层的半径高度小于上一层的半径和高度并且大于等于m-u（m为总层数，u为搜索完的层数，m-u就是剩下的层数(包括这一层) ）。
下面就是要探讨如何进行这三个剪枝：
求剩下层(设为k)的最小体积时，采用递推的方法，由剩下的k-1层的最小体积加上本层的最小体积（i*i*i）。我们用va[i]表示从上往下数前i层的最小体积和，但要注意并不是前i层的最小体积和，因为本题规定的是从下往上数层数。所以实际用时要用v+va[m-u]。
经过一步步的写(kan)证(ti)明(jie)，以下的内容显然成立：剩下层(包含当前层)的最小表面积就小于等于2*(n-v)/r。其中n是总体积，v是现在的体积（不包含当前层），r是当前层的最大半径。为什么是小于等于呢？因为为了保证剪枝的正确性，即使少剪几个，也不能把正确的答案剪去。
总结：剪枝要用最好的打算去进行启发式剪枝。即为了保证剪枝的正确性，即使少剪几个，也不能把正确的答案剪去。
剩下的就是细节处理了，例如在dfs函数中枚举的r和h的值，为什么要倒序呢？因为很显然，在体积一定的情况下，半径越大，侧表面积就越小，能在剪枝2中，剪去更多的枝。（多读几遍，感性理解一下）。
看代码（详细注解）：
#include<iostream>
#include<cmath>
using namespace std;
const int INF=0x3f3f3f;//一个很大的数
int n,m;
int va[];//va[i]表示从上往下数前i个数的最小体积和。(并不是第i层)
int ans;
void dfs(int u,int v,int s,int r0,int h0){
//u为已经搜完的层数,v是现在的体积,s是现在的表面积(所求的)
//r0是当前层的最大半径，h0是当前层的最大高度。
if(u==m){ //如果已经搜完
if(v==n){ //如果找到答案,更新ans的值
ans=min(ans,s);//取最小值
}
return; //无论是不是答案，都要return
}
if(va[m-u]+v>n) return;
//剪枝1：如果当前的体积加上剩下层(包含当前层)的最小体积还是大于要求的总体积时，必须return，因为不论如何体积总不能符合要求。
if(2.0*(n-v)/r0+s>ans) return;
//剪枝2：如果当前表面积加上剩下层(包含当前层)的最小表面积还是大于已经求出来的答案时，return，因为此答案一定不是最优解。
for(int r=r0;r>=m-u;r--){ //从最大值倒着循环速度会快些
for(int h=h0;h>=m-u;h--){
//剪枝3：缩小每一层的体积和高的范围：从r0、h0到m-u。
int tv=v+r*r*h; //tv是现在的体积，就等于原来的体积加上这一层的体积
if(tv>n) continue; //边界
int ts=s+*r*h; //ts为现在的表面积，等于原来的表面积加上这一层的侧表面积
if(u==) ts+=r*r; //如果是底层，还要再加上上表面积
dfs(u+,tv,ts,r-,h-);
//继续递归下去：层数+1,现在的体积,现在的表面积,下一层的最大体积和表面积
}
}
}
int main()
{
cin>>n>>m;
for(int i=;i<=m;i++){
va[i]=va[i-]+i*i*i;//i*i*i是每一层的最小体积
}
int r0=sqrt(n)+0.5;//r0是最大的半径
ans=INF;//先给ans赋初值
dfs(,,,r0,n);
if(ans==INF) ans=;//无答案输出0
cout<<ans<<endl;
return ;
}
//NOI1999 Day1 t3