Codevs 1710 == POJ 1190 生日蛋糕 == 洛谷P1731

生日蛋糕

时间限制: 2 s　　空间限制: 128000 KB　　题目等级 : 大师 Master

题目描述 Description

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外，以上所有数据皆为正整数）

输入描述 Input Description

有两行，第一行为N（N<=10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M<=20)，表示蛋糕的层数为M。

输出描述 Output Description

仅一行，是一个正整数S（若无解则S=0）。

样例输入 Sample Input

100
2

样例输出 Sample Output

数据范围及提示 Data Size & Hint

体积V=πR^2H

侧面积A’=2πRH

底面积A=πR^2

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int n,m,mins[25],minv[25],bests;
 6 void dfs(int v,int s,int level,int r,int h)
 7 {
 8     if(level==0)
 9     {
10         if(v==n)
11           bests=min(bests,s);// 更新最优解
12         return ;
13     }
14     if(v+minv[level-1]>n||s+mins[level-1]>bests||2*(n-v)/r+s>=bests)// 剪枝  前两个比较好想，第三个剪枝也是看了题解才知道
15       return ;
16     int i,j,hh;
17     for(i=r-1;i>=level;i--)
18     {
19         if(level==m)
20             s=i*i;
21         hh=min((n-v-minv[level-1])/(i*i),h-1);
22         for(j=hh;j>=level;j--)
23           dfs(v+i*i*j,s+2*i*j,level-1,i,j);    // v表示当前的体积  s表示当前的表面积
24     }
25 }
26 int main()
27 {
28     mins[0]=0;minv[0]=0;// 计算可能的最小值
29     for(int i=1;i<=20;i++)//  仅仅是理想状态下的最小值
30     {
31         mins[i]=mins[i-1]+2*i*i;
32         minv[i]=minv[i-1]+i*i*i;
33     }
34     while(scanf("%d%d",&n,&m)==2)
35     {
36         bests=0x7fffffff;
37         dfs(0,0,m,n+1,n+1);
38         if(bests==0x7fffffff)
39           printf("0
");
40         else printf("%d",bests);
41     }
42     return 0;
43 }

思路：深搜加剪枝，最下往上搜索，level表示当前搜索到了哪一层