[NOI1999]生日蛋糕

很综合的一道搜索题

从下往上搜
记$v\left [ k \right ]$为1-k 层最小体积，$s\left [ k \right ]$为1-k 层最小面积
记$V$为剩余体积，$S$为当前面积
对于第$k$层

$$h_{k}\in \left [ k,min\left ( h_{k+1} -1,\frac{V-v\left [ k-1 \right ]}{k^{2}}\right ) \right ]$$ $$r_{k}\in \left [ k,min\left ( r_{k+1}-1,\sqrt{\frac{\left ( V-v\left [ k-1 \right ] \right )}{h_{k}} }\right )\right ]$$

可行性剪枝

• 若$V>v\left [ k \right ]$，则返回

最优化剪枝

• 若$S+s\left [ k \right ]>ans$，则返回
• 若$S+\frac{2V}{r_{k+1}}>ans$，则返回

对于最后一种剪枝的证明

$$\sum_{i=1}^{k}2r_{i}h_{i}>\frac{2}{r_{k+1}}\sum_{i=1}^{k}r_{i}^{2}h_{i}=\frac{2V}{r_{k+1}}$$

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF=1<<30,N=20;
int n,m,v[N],s[N],ans=INF;
void dfs(int V,int k,int H,int R,int S)
{
    if (k<=0)
    {
        if (!V) ans=min(ans,S);
        return;
    }
    if (V<v[k]) return;
    if (S+s[k]>ans) return;
    if (S+2*V/R>ans) return;
    for(int h=min(H-1,(V-v[k-1])/(k*k));h>=k;h--)
        for(int r=min(R-1,(int)sqrt((V-v[k-1])/h));r>=k;r--)
            dfs(V-r*r*h,k-1,h,r,S+2*r*h+r*r*(k==m));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        v[i]=v[i-1]+i*i*i;
        s[i]=s[i-1]+2*i*i;
    }
    dfs(n,m,INF,INF,0);
    printf("%d\n",ans==INF?0:ans);
    return 0;
}