题目描述
有一个M层的生日蛋糕，它的体积为Nπ，它每层的半径随层数增加而增加，我们要在蛋糕外表面（出最后一层底面外）涂抹奶油，求蛋糕上涂抹奶油的面积最小为多少。输出Q表示涂抹面积为Qπ。
思路
dfs的剪枝主要包括5类，优化搜索顺序，排除等效冗余，可行性剪枝，最优性剪枝，记忆化。
这道题我们主要运用前四个剪枝。
1、上下界剪枝
当我们递归到第dep层时，我们只需要从以下范围枚举
先枚举R∈[ dep ， min{，r[ dep + 1] - 1}]
再枚举H∈[ dep ， min{/R，r[ dep + 1] - 1}]
这里R和H的下界是比较显然的，而上界都可以由公式πRH = π（N - v）得到
2、优化搜索顺序
这是这道题最重要的优化，虽然简单，却大大提高了搜索效率。在loj上测试，正序搜索总时间1300ms+，倒序搜索总时间9ms。
倒序搜索可以快速得到较优解，从而结合其他剪枝避免了次优解的过多更新，但这里的严谨证明很复杂，作为OIer我们可以通过造数据来测试哪一种搜索
顺序更快。
3、可行性剪枝
我们可以预处理出还剩下dep层的最小体积minv[dep]，这样就有了以下剪枝：
minv[ dep ] + v>N 直接return
4、最优性剪枝
①与可行性剪枝类似，我们可以预处理出还剩下dep层的最小表面积mins，如果mins[dep] + s>ans，可以return。
②这个剪枝就比较复杂，需要一定的数学推导
首先利用h和r数组，1~dep-1的体积可表示为：
同时，1~dep-1层的表面积可表示为：
而显然我们可以得到
由于对于任意k∈[ 1， dep - 1]，r [ k ]都大于r [ dep ]，所以：
而后面的求和公式即为我们上面提到的N - v，所以联立可得：
所以当这个值加目前的表面积s大于ans时可以剪枝。
这个剪枝的效率也相当高，未加此剪枝时间1350ms+。
代码
#include <bits/stdc++.h> using namespace std; int n,m,ans=0x7fffffff; int mins[30],minv[30]; bool check1(int d,int s) { if(mins[d]+s>ans)return 1; return 0; } bool check2(int d,int v) { if(minv[d]+v>n)return 1; return 0; } void dfs(int dep,int s,int v,int r,int h) { if(dep==0) { if(v==n&&s<ans)ans=s; return ; } if(check1(dep,s)||check2(dep,v))return ; if(2*(n-v)/r+s>ans)return ; for(int R=min((int)sqrt(n-v),r-1);R>=dep;R--) { if(dep==m)s=R*R; for(int H=min((int)(n-v)/(R*R),h-1);H>=dep;H--) // cout<<H<<' '<<R<<endl; dfs(dep-1,s+2*R*H,v+R*R*H,R,H); } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { mins[i]=mins[i-1]+2*i*i; minv[i]=minv[i-1]+i*i*i; } // for(int i=1;i<=m;i++) // printf("%d %d\n",mins[i],minv[i]); dfs(m,0,0,n+1,n+1); printf("%d",ans); return 0; }