学步园

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 = πR²H
侧面积A' = 2πRH
底面积A = πR²

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int inf=(1<<31)-1;//const int inf=0x7fffffff
int minv[21],mins[21];//从第一层到第i层的最少面积和最少体积
int cnt;//最少面积
int n,m;
void init()
{
    //第i层的半径和高度最小都为i
    for(int i=1;i<=20;i++)//1-20层
    {
        mins[i]=mins[i-1]+2*i*i;
        minv[i]=minv[i-1]+i*i*i;
    }
}
//搜索高度，上次半径，上次高度，剩余体积，总面积  lev(20-1)
void dfs(int lev,int last_r,int last_h,int leave_v,int sum_s)
{
    if(lev==0)//搜到末尾
    {
        if(leave_v==0) cnt=cnt<sum_s?cnt:sum_s;
        return ;
    }
    //如果当前面积加上后面最少面积大于最小面积或者当前剩余体积小于还需最少体积，直接剪掉
    if(sum_s+mins[lev]>=cnt||leave_v<minv[lev]) return ;

    for(int i=last_r-1;i>=lev;i--) //枚举这一层的半径，最少为lev
    {
        int h=int((leave_v-minv[lev-1])*1.0/i*i);
        h=h<last_h-1?h:last_h-1;//计算最大高度
        for(int j=h;j>=lev;j--)//没聚到这一层的高度，最少为lev
        {
            int s=2*i*j,v=i*i*j;
            if(sum_s+s+mins[lev-1]>=cnt) continue;  //剪的不够
            //这个剪枝很重要，剩余体积为vv=sigma(r*r*h),ss=sigma(2*r*h)=2*vv/r,越大，ss越小
            if(sum_s+s+2*(leave_v-v)/i>=cnt) continue;
            if(lev==m) s+=i*i;
            dfs(lev-1,i,j,leave_v-v,sum_s+s);
        }
    }
}
int main()
{
    init();
    while(scanf("%d%d",&n,&m)==2)
    {
        int t=int(sqrt(n+0.5));//最大半径和最大高度
        cnt=inf;
        dfs(m,t,t,n,0);
        if(cnt==inf) printf("0/n");
        else printf("%d/n",cnt);
    }
    return 0;
}