题解 P1731 【生日蛋糕】

· · 题解 

#include<cstdio>
#include<cstdlib>
using namespace std;
#define MAXN 20005
#define MAXM 16
int n,m;
int Vmin[MAXM+1];
int ans=999999999;//记得初始化一个特别大的值 
void dfs(int dep,int r,int h,int s,int v)//还剩下x层，之前一层半径r，高度h，s 为到了这里时的表面积  v 为剩余的体积 
{
    //剪枝 
    if(Vmin[dep] > v)    return;     //最小都不能构造完 cut 
    // r h 为之前的数据  r-1 h-1 是现在的最大值 
    if(dep*(r-1)*(r-1)*(h-1) < v)    return;//如果剩余的体积太大的话，连之后的每层的体积较这一层都没有少都不能用完则 cut 
    //本来剪枝要更细的  但是由于复杂度高  而且难算难想 所以我们把界限可以放宽一点 
    //v == 0其实可以不加 因为当 dep = 0 则Vmin[dep] = 0  dep*(r-1)*(r-1)*(h-1) = 0 那么v >（或者<0） 0 不满足 所以v = 0
    if(dep == 0 && v == 0){
        if(s < ans) ans = s;            
        return ;
    }
    //枚举r 和 h 
    /*for(int i=dep;i*i*dep<=v;i++){
        if(s + 2 * v / i > ans)    continue;
        for(int j=dep;i*i*j<=v;j++)
                dfs(dep-1,i,j,s+2*i*j,v-i*i*j);
    }*/
    //枚举当前一层的半径 
    for(int i=dep;i<r;i++){//不写上面的那种 是因为 <r <h  更优，而且不满足的话 在上面的if一定会被cut  v 会变负数  
        if(s + 2 * v / i > ans)        continue;    //可行性剪枝 
        for(int j=dep;j<h;j++)                //枚举当前一层的高度 
            dfs(dep-1,i,j,s+2*i*j,v-i*i*j);
    }    
}

/* //注意下面的字母有些地方时有下划线的

怎样求剩余部分侧面积下限？

V=Ri+12*Hi+1+Ri+22*Hi+2+…+Rm2*Hm

2V=Ri+1*Si+1+Ri+2*Si+2+…+Rm*Sm

2V＜Ri+1*S总min

即S总min＞2V/Ri+1

*/

int main()
{
    scanf("%d%d",&n,&m);
    //枚举底层的r和h 
    //记得初始化Vmin数组
    Vmin[0] = 0; 
    for(int i=1;i<=m;i++)//Vmin是这一层最小的体积        1~m   是从上到下 
        Vmin[i]=Vmin[i-1]+i*i*i;
    //i*i*m == n 是可以的  即只有一层 
    for(int i=m;i*i*m<=n;i++)//i*i*m<n 代表的是如果最底下那层的体积都>n  那么肯定不用考虑了 其他的情况后面有考虑和剪枝
        for(int j=m;i*i*j<=n;j++)
            dfs(m-1,i,j,i*i+2*i*j,n-i*i*j);//注意到这里已经用了一层了  所以是m-1 
    //特别注意: 由于是总共的表面积，那么除了侧面积之外还有每一层的上表面 把它们平移往上则是底层的底面积 而底层是不用涂的
    //所以只需要 也必须要+i*i 
    //由于圆周率是相同的    所以同时约去是没有影响的 
    printf("%d",ans);
        return 0;
}