题面
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。
设从下往上数第i层蛋糕是半径为Ri, 高度为Hi的圆柱。
当i < M时，要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ ，请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
除Q外，以上所有数据皆为正整数 。
输入格式
输入包含两行，第一行为整数N（N <= 10000），表示待制作的蛋糕的体积为Nπ。
第二行为整数M(M <= 20)，表示蛋糕的层数为M。
输出格式
输出仅一行，是一个正整数S（若无解则S = 0）。
数据范围
1≤N≤10000,
1≤M≤20
输入样例：
100
2
输出样例：
68
思路
这个题目的思路很明确，从下往上递归每一层，到最上面的时候结束递归。大概可以想到我们在dfs里面需要枚举的是一个每层蛋糕的r和h，那么r和h的范围是我们要确定的第一个点，首先体积限制和面积限制是我们要考虑的点，根据这两个我们可以推出r和h的范围，然后我们考虑最小的放蛋糕的情况，就是每次之比下面的半径和高度小1，然后利用这个条件进行剪枝。最后我们有一个最重要的剪枝，需要推导一下不等式，计算一下剩余体积最大和面积最大的限制，进行一个比较然后形成一个放缩不等式，进行一个最优化剪枝。总结一下搜索剪枝类问题的顺序，就是先开始最重要的是建立搜索模型或者说清楚搜索步骤，大概知道dfs函数里面的参数，并且知道递归结束的return怎么写，然后我们考虑优化一些搜索顺序，可行性剪枝，最优化剪枝等一一系列剪枝技巧。
代码实现
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair <int ,int> PII;
const int maxn=20;
const int inf=0x3f3f3f3f;
int n,m;
int mins[maxn],minv[maxn];
int R[maxn],H[maxn],ans=inf;
void dfs (int u,int v,int s) {
if (v+minv[u]>n) return ;
if (s+mins[u]>ans) return ;
if (s+2*(n-v)/R[u+1]>=ans) return;
if (!u) {
if (n==v) ans=s;
return ;
}
for (int r=min ((int )sqrt (n-v),R[u+1]-1);r>=u;r--)
for (int h=min ((n-v)/r/r,H[u+1]-1);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;
mins[i]=minv[i-1]*i*i*2;
}
R[m+1]=H[m+1]=inf;
dfs (m,0,0);
if (ans==inf) cout<<0<<endl;
else cout<<ans<<endl;
return 0;
}