参考：点击打开链接
作者：1300012964
<pre name="code" class="cpp">/*
生日蛋糕
查看 提交 统计 提问
总时间限制: 5000ms 内存限制: 65536kB
描述
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 = πR2H
侧面积A' = 2πRH
底面积A = πR2
思路：
设最底层为M层
逐个尝试底层蛋糕的大小，R，H，剩余体积(即为rest_V）减小，面积增大，
继续求解剩余体积下，直至V==0，此时获得一个s,用一个res比较,尝试所有的情况,获得最小的S
初始我们给出体积为V,层数为M,所以我们知道第M层的半径R>=M且H>=M,
所以我们可以通过第M层圆柱的体积R^2*H_max=Vm<V 得出第M层高H的最大值H_max<V/(R*R)+1 ,
同理可以推出R_max<srqt(V/M)+1.
枚举时下一层的r和h 都必须比上一层的小
单单这样搜索，很容易TLE,必须剪枝
剪枝一：
如果剩下的体积只作成一个圆柱体的话，得到的侧面积是最小的
但是这种情况下所得的侧面积还是比res大的话，则剪枝
此时的最小侧面积的算法为 2*rest_V/(pre_R-1)--->这里r=pre_R-1最大，s最小
剪枝二:
如果剩余的最上面几层的最小体积大于剩余的体积rest_V，则退出
上面floor层的最小体积用Min_V[floor]记载，则每一层的r，h取floor
如果当前的面积加上剩余最上面几层的最小面积大于最小面积res，则退出
上面floor层的最小体积用Min_S[floor]记载，则每一层的r，h取floor
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int N,M;
int res = 9999999;
int Min_V[22],Min_S[22];
void Search(int rest_V,int curr_S,int floor,int pre_R,int pre_H)
//pre_R和pre_H为上一层蛋糕的R和H
{
if(floor == 0)
{
if(rest_V == 0 && curr_S < res)
res = curr_S;
return;
}
//剪枝一：
if(pre_R > 1 && 2*rest_V/(pre_R-1) + curr_S > res)
return;
//剪枝二：
if(rest_V < Min_V[floor] || curr_S + Min_S[floor] >= res)
return;
for(int r = pre_R - 1;r >= floor; --r)
{
if(floor == M)
curr_S = r*r;
for(int h = pre_H - 1; h >= floor; --h)
Search(rest_V-r*r*h,curr_S+2*r*h,floor-1,r,h);
}
}
int main()
{
scanf("%d%d",&N,&M);
Min_S[0] = Min_V[0] = 0;
for(int i = 1; i <=20; ++i)
{
Min_S[i] = Min_S[i-1] + i*i;
Min_V[i] = Min_V[i-1] + i*i*i;
}
int MaxR = sqrt(1.0*N/M) + 1;
int MaxH = (1.0*N)/(M*M) + 1;
Search(N,0,M,MaxR,MaxH);
if(res == 9999999)
printf("0\n");
else
printf("%d\n",res);
system("pause");
return 0;
}
<pre name="co
