【题目描述】
7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。 设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。 由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 令Q = Sπ 请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。 （除Q外，以上所有数据皆为正整数）
【题目链接】
【算法】
dfs剪枝。
1）搜索顺序：自下往上，自大往小。（自小往大就玄学的T和R了qwq）
2）上下界剪枝：R和H的枚举控制范围
3）可行性剪枝a：当前体积加上未计算层的最小体积超过n，剪枝
4）可行性剪枝b：当前体积加上未计算层的最大体积小于n，剪枝
4）最优性剪枝：当前表面积加上最小表面积超过ans，剪枝
5）高级最优性剪枝：数学公式推导一波
改掉头文件后，loj14ms。。。。（还可以输入优化，不过感觉没必要）
【代码】
#include <bits/stdc++.h>
using namespace std;
int n,m,ans=1e9;
int recv[25],recs[25],h[25],r[25];
int cal(int h,int r,int dep) {
if(!dep) return 0;
return r*r*h+cal(h-1,r-1,dep-1);
}
void dfs(int dep,int s,int v) {
if(dep==0) {
if(v==n) ans=min(ans,s);
return;
}
for(int R=min(r[dep+1]-1,(int)(sqrt(n-v)));R>=dep;R--) {
for(int H=min(h[dep+1]-1,(n-v)/(R*R));H>=dep;H--) {
int curv=R*R*H,curs=2*R*H;
if(v+curv+recv[dep-1]>n) continue;
if(s+curs+recs[dep-1]>=ans) continue;
if(s+curs+2*(n-v-curv)/R>=ans) continue;
if(v+curv+cal(H-1,R-1,dep-1)<n) break;
h[dep]=H,r[dep]=R;
if(dep==m) s=R*R;
dfs(dep-1,s+curs,v+curv);
if(dep==m) s=0;
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) recv[i]=i*i*i+recv[i-1],recs[i]=2*i*i+recs[i-1];
h[m+1]=r[m+1]=1e9;
dfs(m,0,0);
printf("%d\n",ans);
return 0;
}