题目描述

7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。

设从下往上数第i层蛋糕是半径为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）。

数据范围
1≤N≤10000,
1≤M≤20

样例

输入样例：
100
2
输出样例：
68

搜索+剪枝

整个计算忽略π

同样是暴搜，从下到上，递减搜索半径和高度。总体积固定，从大的开始搜索范围会更小。
dfs记录状态，当前搜索到了第几层，当前总面积是多少，总体积是多少。

设最底层是第M层，则第depth层的半径最大应该为min(R(depth+1)-1,sqrt(N-v))，而最小的一层最小也为1，所以第depth层最小为depth;
高度最大为min(floor((N-v)/pow(R,2)),H(depth+1)-1),同理，最小为depth;

在枚举的时候始终秉承先枚举决策种数少的，则先枚举R，因为R是平方，数据更大，而总量不变。

剪枝：
1.如果当前层的最小体积+已有的体积>N，最小体积，最小面积就是对半径和高度取当前能取得最小值进行计算
2.如果当前层的面积+已有的面积>ans(前面已经搜索完毕得到的总面积大小)
3.当前层数depth，体积v，面积s，考虑不等式

C++ 代码

#include<iostream>
#include<math.h>
using namespace std;

const int N=25;
const int inf=1e9;

int n,m;
int R[N],H[N];
int minv[N],mins[N];//前i层体积，面积最小分别为多少
int ans=inf;

void dfs(int u,int v,int s){
    if(minv[u]+v>n)    return;
    if(s+mins[u]>ans)    return;
    if(!u){
        if(v==n)    ans=s;
        return;
    }
    if(s+2*(n-v)/R[u+1]>ans)    return;

    for(int r=min(int(sqrt((n-v))),R[u+1]-1);r>=u;r--){
        for(int h=min(int((n-v)/r/r),H[u+1]-1);h>=u;h--){
            int t=0;
            if(u==m) t=r*r;
            R[u]=r;
            H[u]=h;
            dfs(u-1,v+r*r*h,s+2*r*h+t);
        }
    }
}
int main(){
    cin>>n>>m;
    //初始化minv,mins
    for(int i=1;i<=m;i++){
        minv[i]=minv[i-1]+i*i*i;
        mins[i]=mins[i-1]+2*i*i;
    }
    //注意边界
    R[m+1]=inf;H[m+1]=inf;
    dfs(m,0,0);//从最下面一层开始搜索，当前的体积和面积都是0

    cout<<ans<<endl;
    return 0;
}