jop：1190 生日蛋糕
- 题目要求
- 分析
- 源代码
题目要求
要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1 <= i <= M)层蛋糕是半径为R[i], 高度为H[i]的圆柱。当i < M时，要求R[i]>R[i+1]且H[i]>H[i+1]。由于要在蛋糕上抹奶油，为尽可能节约经费，希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q = Sπ，请编程对给出的N和M，找出蛋糕的制作方案（适当的R[i]和H[i]的值），使S最小，也就是求出蛋糕除了下底面的表面积最小是圆周率的多少倍？
除Q外，以上所有数据皆为正整数。
输入要求
输入有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。
输出要求
输出仅一行，是一个正整数S（若无解则S = 0）。
输入输出格式请参考原题页面。
要求使用递归-回溯算法，并在算法中尽可能引入尽可能多的剪枝措施。
题目链接：http://poj.org/problem?id=1190
分析
首先自下而上来建一个蛋糕。设蛋糕有M层，最下面一层半径r，高度h。
从下往上看，半径的最大值分别为r、r-1、…、r-M+1。高度的最大值为h、h-1、…、h-M+1。
同理，也有最小值，半径的最小值分别为M、M-1、…、1。高度的最小值为M、M-1、…、1。
从上往下看，设minV【i】表示从上往下的前i层的体积最小值，minA【i】表示前i层的侧面积的最小值。则有递推公式：
minV【i】=minV【i-1】+π*i的3次方；
minA【i】=minA【i-1】+2* π*i的2次方；
注意边界条件minV【0】=0,minA【0】=0。
蛋糕上需要涂奶油的表面积，正好就是蛋糕最底层的上表面积，因此可以将最底层的上表面积的值，作为蛋糕总表面积area的初始值。往后只需要累加每一层的侧面积即可。这里使用递归回溯法进行深度优先搜索。设DFS（int v,int top,int r,int h）表示搜索过程，其中：
v表示还要搭建多少体积；
top表示还要搭建的层数；
r表示自下而上搭建时，即将要搭建的这一层的半径可能的最大值；
h表示自下而上搭建时，即将要搭建的这一层的高度可能的最大值。
在搜索时，需要枚举当前搭建的这一层的半径和高度。设半径currentR∈【top,r】，高度currentH∈【top,h】。由于从下往上每一层的半径和高度都是递减的，所以currentR和currentH需要倒叙枚举。
由圆柱体侧面积公式可得，当前搭建的这一层的侧面积为2πcurrentRcurrentH。将这个值累加如总表面积area。接下来的过程，可以递归表示为DFS（v-currentRcurrentR*currentH,top-1,currentR-1,currentH-1）。
由于当前搭建的这一层的半径和高度，currentR和currentH的范围太大，解空间树分值太多，必须想办法进行剪枝。遇到下列情况必须剪枝：
- 当还要搭建的层数top为0，但是还要搭建的体积v不为0时；
- 还没搭建完所有的层，蛋糕体积已经超过了指定体积；
- 还要搭建的体积 v<还要搭建的层数的总体积的最小值minV【top】，那么还要搭建的体积满足不了上面top层的最小体积；
- 已经搭建好的部分蛋糕的面积area，加上还没搭建的蛋糕至少需要的表面积minA【top】,超过了目前已经求得的最少表面积；
- 由于每一层的高度和半径都必须是整数，若h<top或者r<top，表示再往上搭建蛋糕，高度或者半径无法满足条件；
- 需要搭建的共top层的蛋糕体积的最大值小于v，即剩下还没搭建的那部分体积，无论如何搭建都无法达到还缺少的体积v。
最后注意：题目需要计算涂抹奶油的蛋糕的外表面的饿面积是多少π，因此计算过程中，可忽略π。
源代码
#include
#include
#include
#include
#include
using namespace std;
class Cake//定义一个解题类
{
protected:
int N;//题目要求中需要构建的蛋糕的体积
int M;//题目要求中需要构建的蛋糕的层数
int* minA;//数组，minA[i]表示共i层的蛋糕可能的最小侧面积
int* minV;//数组，minV[i]表示共共i层的蛋糕可能的最小体积
int minArea;//搜索过程中的一个最优值，也就是蛋糕涂抹的奶油面积的最小值
int area;//在搭建蛋糕过程中，已经搭建的蛋糕的表面积
int MaxVForNRH(int n,int r,int h) const;//计算在蛋糕有n层，底面最大半径r,最大高度h的情况下，能凑出来的最大体积
void DFS(int v,int top, int r, int h);//深度优先搜索+剪枝函数，还需要搭建的体积v,还需要搭建的层数top，正在搭建的那一层的半径最大值r，同层高度最大值h
void Init();//初始化
public:
void Solve();//求解整个测试用例的方法
};
//计算在蛋糕有n层，底面最大半径r,最大高度h的情况下的最大体积
int Cake::MaxVForNRH(int n,int r, int h) const
{
int v=0;
for(int i=0;i<n;i++)//从上往下的遍历每一层
{//从下往上的第i层的半径最大值为r-i，高度为h-i
v+=(r-i)(r-i)(h-i);
}
return v;
}
//初始化，将每一层的最小体积和最小侧面积算出来
void Cake::Init()
{
area=0;
minArea=INT_MAX;//涂抹奶油的最小表面积会不断递减，初始化为无穷大
minV[0]=0;minA[0]=0;//边界条件
for(int i=1;i<=M;i++)//从上到下遍历每一层
{
minV[i]=minV[i-1]+iii;//从上往下的前i层最小体积等于，前i-1层的最小体积加上，当前的体积i的三次方
minA[i]=minA[i-1]+2ii;//同上
}
}
//深度优先搜索+剪枝，注意搜索的半径要从大到小，否则超时
//v：还需要搭建的体积
//top：还需要的层数
//r:自下而上搭建时，即将要搭建的这一层的半径可能的最大值
//h:自下而上搭建时，即将要搭建的这一层的高度可能的最大值
void Cake::DFS(int v,int top,int r,int h)
{
if(top0)//需要搭建的层数为0，就是搭建完了，不需要再搭建了
{
if(v!=0)//但是需要搭建的体积还没完，不合理，剪枝
{
return;
}
else//需要搭建的体积也为0，得到一种搭建方案
{
minArea=min(minArea,area);//若是新方案中涂抹奶油的面积area小于原先最小的涂抹奶油的面积，就将area赋值给最小面积minArea
return;
}
}
//还没有搭建完层数，搭建出来的体积已经超过了题目指定体积，剪枝
if(v<=0) return;
//还没有搭建的那些层数的最小体积超过了还缺少的体积，剪枝
if(minV[top]>v) return;
//已经搭建好的蛋糕的表面积加上还没搭建的蛋糕至少需要的表面积，超过了目前求得的最小表面积，剪枝
if(area+minA[top]>=minArea) return;
//每一层的高度和半径都必须是整数，再往上搭建蛋糕的高度或者半径都无法满足条件，剪枝
if(h<top||r<top) return;
//剩下还没搭建的那些体积，无论如何构造都无法达到缺少的体积，剪枝
if(MaxVForNRH(top,r,h)<v) return;
for(int currentR=r;currentR>=top;currentR–)//枚举出底面积的半径，自下而上每一层半径递减，倒叙循环
{
if(topM)//如果刚开始搭建，将最下层的底面积作为外表面积的初始值
{
area=currentRcurrentR;
}
for(int currentH=h;currentH>=top;currentH–)//枚举底层高度，自下而上每一层高度递减，倒叙循环
{
int flank=2currentRcurrentH;//定义flank，计算当前搭建的这一层的侧面积
area+=flank;//累加每一层的侧面积到area中
DFS(v-currentRcurrentRcurrentH,top-1,currentR-1,currentH-1);//递归搜索搭建上一层
area-=flank;//恢复area的值
}
}
}
void Cake::Solve()//求解所有测试用例的过程函数
{
while(cin>>N>>M)//读入N和M的值
{
minV=new int[M+1];minA=new int[M+1];//分配存储单元
Init();//初始化
if(minV[M]>N)//要搭建的M层蛋糕的体积超过了题目给定的体积
cout<<0<<"\n";//题目无解，输出0，换行
else
{
int maxH=(N-minV[M-1])/(MM)+1;//定义变量，计算最底层的可能的最大高度，其中N指所有的层加起来的总体积，minV[M-1]表示从上往下前M-1层体积的最小值，(N-minV[M-1])则表示最下面那一层的最大体积；M表示最下面那一层的最小半径，(M*M)便是最下面那一层的最小面积；+1是防止不整除时向下取整
int maxR=(int)sqrt(double(N-minV[M-1])/M)+1;//同理，计算最底层的可能最大半径。/M中的M表示最下层的最小高度，sqrt表示开根
DFS(N,M,maxR,maxH);
if(minArea==INT_MAX)//意味数据不合法，没有搜索到最优值
cout<<0<<"\n";
else cout<< minArea<<"\n";
}
delete[] minA;delete[] minV;//动态释放空间
}
}
int main()
{
Cake obj;
obj.Solve();
return 0;
}
