「一本通 1.3 例 2」生日蛋糕（深搜+剪枝）

题目描述

Mr.W 要制作一个体积为Nπ的M 层生日蛋糕，每层都是一个圆柱体。

设从下往上数第 i蛋糕是半径为Ri ，高度为 Hi的圆柱。当i<M时，要求Ri>Ri+1且Hi>Hi+1 。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 Q 最小。 令 Q=Sπ，请编程对给出的 N和 M ，找出蛋糕的制作方案（适当的 Ri 和 Hi 的值），使 S 最小。（除 Q 外，以上所有数据皆为正整数）

输入格式

第一行为 N ，表示待制作的蛋糕的体积为Nπ ；

第二行为 M ，表示蛋糕的层数为M 。
输出格式
输出仅一行，一个整数 （若无解则 ）。
样例

样例输入
100
2
样例输出
68
附：圆柱相关公式：
体积V=π*RRH
侧面积S1=2πRH ；
底面积S=πRR 。

数据范围与提示
对于全部数据，1<=N<=10000,1<=M<=20。

代码：

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int n,m;
int minn=1e9;
void dfs(int num,int s,int v,int lastr,int lasth)
{
    //num为正在搜索蛋糕第num层,s为当前表面积,v为当前体积,lasth为上一层的高,lastr为上一层的半径//int i,j;if(num==m+1&&v==n)  //层数达到m层且体积也相等{
    minn=min(minn,s); //记录最小的表面积return;}if(v>=n) //如果当前体积大于n,直接返回return;int t=m-num+1;//还有剩余t层没有安排if(v+t*lastr*lastr*lasth<n) //如果当前的体积加上最大体积仍然小于要求体积,不符合条件,返回return;if(num==1)  //最底层{
    //i表示半径,j表示高，for(int i=lastr; i>=m; i--)//底层的半径最小为层数m,最大为28{
    for(int j=m; j<=lasth; j++) //底层的高最小为m,最大为28{
    dfs(num+1,s+i*i+2*i*j,v+i*i*j,i,j);}}}else{
    for(int i=lastr-1; i>=m-num+1; i--) //半径最大为比上一层的半径小1，最小为层数{
    for(int j=m-num+1; j<=lasth-1; j++) //高最小为层数，最大为上一层高-1{
    dfs(num+1,s+2*i*j,v+i*i*j,i,j);}}}
}
int main()
{
    scanf("%d",&n);scanf("%d",&m);//int r=(int)sqrt(n/m);dfs(1,0,0,28,28);printf("%d\n",minn);return 0;
}