题解 P1731 【[NOI1999]生日蛋糕】

· · 题解

链接

借这道题来谈谈剪枝：

生日蛋糕这道题的优化方法有如下几种：

1、前缀和优化。用vmin[i]和smin[i]记录前i层及其自身的体积（侧面积）最小情况（即第一层r=1,h=1，第二层r=2,h=2…）的总和，用于后面的剪枝。

2、v+rrh+vmin[i+1]<=n 如果当前的总体积+该层往上的所有的总体积的最小和>给定蛋糕的体积，剪掉。（可行性剪枝）

3、s+2rh+smin[i+1]< best 如果当前的总表面积+该层往上的所有的表面积的最小和>目前最优解,剪掉。（最优化剪枝）

4、v+rrh*(m-i+1)>=n 如果后面的所有层均以当前表面积做成 蛋糕，如果此时的体积仍然小于蛋糕的体积，就要剪掉。（可行性 剪枝）

这种剪枝方法等价于：假设剩余的体积全部以当前层的半径做成蛋 糕，因为当前的半径的最大的，所以得出的表面积是最小的，根据 这个“最小表面积”判断表面积是否超过最优解，超出则剪掉。

5、搜索的顺序:r从大往小循环，h从小往大循环。由侧面积 s=2rh,体积v=rrh得：在s中r的增长是线性的，在v中r的增 长是平方的。r从大往小，h从小往大，可以更快的到达目标 （best）即最优解，之后越多不必要的搜索就会被剪枝，从而提高 效率。

代码

#include<cstdio>
#include<cmath>
using namespace std;
int n,m,best=0x7fffff,vmin[25],smin[25];

void dfs(int i,int ri,int hi,int s,int v)//i当前层数，ri,hi上一层的半径和高，s,v之前的面积，体积总和 
{
    for (int r=m-i+1; r<=ri-1; r++) //最小状态，第i层（从上往下）的半径和高度均为i 
        for (int h=hi-1; h>=m-i+1; h--)
        {
            if (i==1) s=r*r;
            if (s+2*r*h+smin[i+1]<best&&v+r*r*h+vmin[i+1]<=n&&v+r*r*h*(m-i+1)>=n)
            {
                if (i==m) best=s+2*r*h;
                else dfs(i+1,r,h,s+2*r*h,v+r*r*h);
            }
        }
}
int main()
{
    scanf("%d%d",&n,&m);
    vmin[0]=0; //第0层的体积和表面积都是0(前缀和技巧？) 
    smin[0]=0;
    for (int i=1; i<=m; i++)//从下往上，m层为最上面的一层 
    {
        vmin[m-i+1]=vmin[m-i+2]+i*i*i;//min[i]表示前i层及其自身的体积（侧面积）的总和，用于剪枝 
        smin[m-i+1]=smin[m-i+2]+2*i*i;//smin只记录侧面积 
    }
    dfs(1,sqrt((n-vmin[2])/m)+1,(n-vmin[2])+1,0,0);//最下面那层的上一层的半径为本层半径+1（高同理）
    printf("%d\n",best);
    return 0;
}