POJ1190:生日蛋糕（深搜+剪枝）

POJ1190:生日蛋糕

描述:

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

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

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

样例输入：

100 2

样例输出：

68

大体思路：

首先题目是给定我们蛋糕的层数和体积，要我们去搭一个蛋糕，在保证每一层都比上面那一层的半径、高度大的前提下，找到使得外表面积最小的一种方案。

那么运用深搜，其实也就是枚举的思想，找到所有方案，取最优的方案。那么这里的深搜的结点就是一个一个状态，这个状态是(v,n,r,h)，表示我们还需要搭n层的体积为v的蛋糕，底层的半径最大为r，底层的高最高为h；那么初始状态是(N,M,r0,h0),结束状态是(0,0,ri,hi)。其中r0和h0是需要我们估计的最大可能的半径和高度。

当然也就需要剪枝，不然很大可能超时。那么首先可行性剪枝有：

当达到某个状态时，不管再如何搭建，体积都大于我们还需要搭建的体积。当达到某个状态时，不管再如何搭建，体积都小于我们还需要搭建的体积。

最优性剪枝： 当达到某个状态时，不管再如何搭建，表面积都小于我们已经求得的最小表面积。当到达某个状态时，表面积已经不小于已经求得的最小表面积。

AC代码

#include<iostream> #include<cstdio> #include<cmath> using namespace std; int N,M; //体积为N，层数为M int minS = 1 << 30; //最小外表面积 int s; //当前外表面积 int tempS[21]={0}; //制作i层的最小表面积 int tempMinV[21]={0}; //制作i层的最小体积 int tempMaxV; //制作i层的最大体积(需要根据上一层的半径和高计算，不能初始化) void dfs(int v, int n, int r, int h) { //边界条件 还需要搭0层 if(n == 0) { if(v != 0) return ; else { if(minS > s) minS = s; return ; } } if(v <= 0) //因为n是每次-1，所以不用判断小于0的状态 return ; //最优性剪枝 //之后的面积一定不会更小 if(s + tempS[n] >= minS) return ; //可行性剪枝 if(tempMinV[n] > v) return ; //循环所有的能到达的结点，也就是状态 for(int rr = r; rr >= n; rr--) //因为还有n层，所以这里半径最小只能是n { for(int hh = h; hh >= n; hh--) { //如果是第一层 那就先s=底面积也就是外表面积的上面的和 if(n == M) s = rr*rr; tempMaxV = 0; //算出最大能得到多大的体积 for(int i = 1; i<= n-1; i++) { tempMaxV += (rr-i)*(rr-i)*(hh-i); } if(v-rr*rr*hh > tempMaxV) continue; s += 2*rr*hh; dfs(v-rr*rr*hh,n-1,rr-1,hh-1); s -= 2*rr*hh; } } } int main() { scanf("%d %d",&N,&M); s = 0; //最大是体积为10000 那么我们先估计最大半径和最大高度 //r = 100,h = 10000; //初始化，便于剪枝 for(int i = 1; i <= 20; i ++) { for(int j = 1; j <= i ;j ++) { tempMinV[i] += pow(j,3); tempS[i] += 2*pow(j,2); } //最大体积只能知道上一层的半径和高才能算 } dfs(N,M,100,10000); if(minS == 1 << 30) printf("0"); else printf("%d",minS); return 0; }