题目背景

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;
}
01-05 02:07