生日蛋糕
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 12277 | Accepted: 4325 |
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外，以上所有数据皆为正整数）
设从下往上数第i(1 <= i <= M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i < M时，要求Ri > Ri+1且Hi > Hi+1。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。
令Q = Sπ
请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。
（除Q外，以上所有数据皆为正整数）
Input
有两行，第一行为N（N <= 10000），表示待制作的蛋糕的体积为Nπ；第二行为M(M <= 20)，表示蛋糕的层数为M。
Output
仅一行，是一个正整数S（若无解则S = 0）。
Sample Input
100
2
Sample Output
68
Hint
圆柱公式
体积V = πR2H
侧面积A' = 2πRH
底面积A = πR2
体积V = πR2H
侧面积A' = 2πRH
底面积A = πR2
#include<stdio.h>
#include<math.h>
#include<string.h>
#define MAXN 999999999
int f,n,mins; int dfs(int m,int r,int h,int s,int v)
{
int i,j,k,a,b,temp;
v+=r*r*h;
if(v>n)
return 1;
s+=2*r*h;//if(v==100)printf("%d %d %d %d %d %d ",m,v,r,h,s,n);
if(s+2*(n-v)/r>=mins)//这是一个很厉害的剪枝，看解题报告的，没这个我的就超时
return 2;//2是除了返回0,1，-1三种情况之外的情况
if(m<f)
{
a=dfs(m+1,r-1,h-1,s,v);//根据返回值来判断当前半径高度都取最大值结果v<=n，那么这种状态则可直接剪掉
if(a==-1)
return -1;//表示v比n小
else if(a==0)
return 0;//表示v等于n
a=dfs(m+1,f-m,f-m,s,v);//根据返回值来判断当前半径高度都取最小值结果v>=n，那么这种状态则可直接剪掉
if(a==1)
return 1;//表示v比n大
else if(a==0)
return 0;//表示v等于n
}
if(m==f)
{
if(v<n)
return -1;
else if(v>n)
return 1;
if(mins>s)
{
mins=s;
}
return 0;
}
else if(v>=n)
return 1;
for(i=r-1;i>=f-m;i--)
{
temp=(n-v)/i/i;
for(j=temp<(h-1)?temp:(h-1);j>=f-m;j--)
{
if((j!=h-1||i!=r-1)&&(j!=f-m||i!=f-m))//这句话是为了避免前面的已经搜索过的重复搜索
dfs(m+1,i,j,s,v);
}
}
return 2;
} int main()
{
int i,j,k,a[30][3],s,v;
while(scanf("%d%d",&n,&f)!=EOF)
{
a[0][0]=sqrt((double)n);
mins=MAXN;
k=0;
v=0;
for(i=a[0][0];i>=f;i--)
{
s=i*i;//先把底面积给加上去
for(j=n/i/i;j>=f;j--)
{
dfs(1,i,j,s,v);
}
}
if(mins!=MAXN)
printf("%d\n",mins);
else printf("0\n");
}
return 0;
}