一本通例题-生日蛋糕——题解<超强深搜剪枝，从无限到有限>

题目传送

显然是道深搜题。由于蛋糕上表面在最底层的半径确认后就确认了，所以搜索时的面积着重看侧面积。

找维度/搜索面临状态/对象：当前体积v，当前外表面面积s，各层的半径r[]，各层的高度h[]。

可行性剪枝考虑/找限制、上下界：

　　　1、考虑当前：当前体积v一定小于总体积N；第i层的半径和高度一定比上一层小（从下往上数层数），同时每次层的高度和半径都>=1(都是正整数)。

　　　2、更近一步，考虑未来：预处理出蛋糕制作到第i层之后再制作的蛋糕体积最小的情况，如果当前体积+这种情况>N，显然不能做成蛋糕;顶层的h、r要大于等于一，而下面每层都要比上面的大，所以h[i]、r[i]>=m-i+1

最优性剪枝考虑：

　　　1、考虑当前：当前面积s小于已搜到的答案ans（否则不会更有，回溯）。

　　　2、更近一步，考虑未来：预处理出蛋糕制作到第i层之后再制作的蛋糕面积最小的情况，如果当前面积积+这种情况>=ans，显然不会更优，回溯。

联系各个维度加强剪枝（简单粗暴的概括：尝试各维度/状态互相表示、将各自的边界融合在一起）：

　1（可行性）：由N-v>=πr²h ，r>=1，h>=1得r<=sqrt(N-v)，h<=(N-v)/r/r（因为最后的Q把π“全包了”，所以可以无视π）（先枚举r，再枚举h）

　　　  2（最优性）：利用h与r数组，dep+1到m层的体积可以表示成n-v=∑（k=dep+1,m）h[k]*r[k]*r[k]，表面积（不算底面积，因为s先前已经算上了）可以表示成2∑（k=dep+1,m）h[k]*r[k]。因为2∑（k=dep+1,m）h[k]*r[k]=2/r[dep]*∑（k=dep+1,m）h[k]*r[k]*r[dep]>=2/r[dep]*∑（k=dep+1,m）h[k]*r[k]*r[k]=2*(n-v)/r[dep], 所以当s+2*(n-v)/r[dep]>=ans时就回溯。

考虑搜索顺序：为了使搜索树较浅的地方分支少，可从底层向顶层搜索。

上AC注释代码:

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int n,m,r[21],h[21],minv[21],mins[21];//层数从下往上数 ,mins仅为侧面积 
int s,v,ans=0x7fffffff;//目前面积、体积，最终答案 

void dfs(int k)//要干第k层 
{
    for(int i=min(r[k-1]-1,(int)sqrt(n-v));i>=m-k+1;i--)//半径r （融合多种剪枝） 
        for(int j=min(h[k-1]-1,(int)((n-v)/(double)i/i));j>=m-k+1;j--)//高度h （融合多种剪枝） 
        {
            if(v+minv[k]>n||s+mins[k]+r[1]*r[1]>=ans||2*(n-v)/(double)r[k-1]+s+r[1]*r[1]>=ans) return;//可行性&最优性剪枝 
            v+=i*i*j; 
            s+=2*i*j;
            r[k]=i;
            h[k]=j;
            if(k!=m&&v!=n) dfs(k+1);
            if(k==m&&v==n) ans=min(ans,s+r[1]*r[1]);
            v-=i*i*j;
            s-=2*i*j;
        } 
}

int main()
{
    cin>>n>>m;
    r[0]=0x7fffffff;h[0]=0x7fffffff;
    for(int i=m;i>=1;i--)//预处理 
    {
        minv[i]=minv[i+1]+(m-i+1)*(m-i+1);
        mins[i]=mins[i+1]+(m-i+1)*2;
    }
    dfs(1);
    if(ans==0x7fffffff) ans=0;//没有解输出0 
    cout<<ans;
    return 0;
}

小总结：仔细分析性质、找状态维度、分析边界、确认好搜索顺序。