信息学奥赛一本通T1441：生日蛋糕

【题目描述】

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=πR2HV=πR2H
侧面积A=2πRHA=2πRH
底面积A=πR2

【源程序】

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 500000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int n,m;
int minn=INF;
//step为前step层，v、s为前step层体积、面积，r、h为第step层半径、高
void dfs(int step,int v,int s,int r,int h){
    if(step==m){//层数搜索完，返回
        if(v==n)//体积为所给体积，更新最小面积
            minn=s;
        return;
    }

    if(v+(r-1)*(r-1)*(h-1)*(m-step)<n)//当前层体积与每层体积最大值之和小于n，不符合，返回
        return;
    if(v+1*1*1*(m-step)>n)//当前层体积与每层体积最小值之和大于n，不符合，返回
        return;
    if(2*(n-v)/r+s>=minn)//侧面积加上前step层面积大于最小值，不符合，返回
        return;

    for(int i=r-1;i>=m-step;i--){//上一层的半径的最小值要保证大于当前层半径的最小值
        for(int j=h-1;j>=m-step;j--){//上一层高度的最小值要保证大于当前层高度的最小值
            int area=s+2*i*j;//面积
            int volume=v+i*i*j;//体积
            if(area<minn&&volume<=n)
                dfs(step+1,volume,area,i,j);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    /*
        i为半径,j为高
        第1层为1,第2层为2,...,第m层为m，故半径最小为m，同理，高最小也是m
        根据题意，蛋糕体积V=n*pi,则半径i的平方i*i为底面积，乘以层数m即为体积
        则有不等式：m*(i*i*pi)<=n*pi，即：i*i*m<=n
        同理，对于高度j，有：i*i*j<=n
    */
    for(int i=m;i*i*m<=n;i++){
        for(int j=m;j*i*i<=n;j++){
            int flankArea=2*i*j;//侧面积
            int bottomArea=i*i;//底面积
            int area=flankArea+bottomArea;
            int volume=i*i*j;//体积
            if(area<minn)
                dfs(1,volume,area,i,j);
        }
    }
    printf("%d\n",minn);
    return 0;
}

信息学奥赛一本通T1441：深搜的剪枝技巧 生日蛋糕 归属于 深搜的剪枝技巧，更多同类题解源程序见：深搜的剪枝技巧 和 生日蛋糕