题目背景
7月17日是Mr.W的生日,ACM-THU为此要制作一个体积为Nπ的M层
生日蛋糕,每层都是一个圆柱体。
设从下往上数第i(1<=i<=M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i<M时,要求Ri>Ri+1
由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积Q最小。
令Q= Sπ
请编程对给出的N和M,找出蛋糕的制作方案(适当的Ri和Hi的值),使S最小。
(除Q外,以上所有数据皆为正整数)
题目描述
输入格式
有两行,第一行为N(N<=20000),表示待制作的蛋糕的体积为Nπ;第二行为M(M<=15),表示蛋糕的层数为M。
输出格式
仅一行,是一个正整数S(若无解则S=0)。
#include<iostream>
using namespace std;
int n,m;int maxn=(1<<31)-1;int f1[1001],f2[1001];
inline void dfs(int dep,int lastr,int lasth,int s,int v){
if(dep==0){if(s<maxn&&n==v)maxn=s;return;}
if(s+2*(n-v)/lastr>maxn)return;
if(f1[dep]+v>n)return;
if(f2[dep]+s>maxn)return;
for(int r=min(n-v,lastr-1);r>=dep;r--)
for(int h=min((n-v)/(r*r),lasth-1);h>=dep;h--)
dfs(dep-1,r,h,2*r*h+s,v+r*r*h);
}
int main(){
cin>>n>>m;
for(int i=1;i<m;i++){f1[i]=i*i*i+f1[i-1];f2[i]=2*i*i+f2[i-1];}
for(int r=n;r>=m;r--)
for(int h=n/(r*r);h>=m;h--)
dfs(m-1,r,h,r*r+h*2*r,r*r*h);
cout<<maxn;
}