题解 P1731 【生日蛋糕】

· · 题解

这道搜索水题 有点干燥

几百年前的全国赛怎么比现在的容易这么多 虽然我就是个普及蒟蒻 但是居然做出来了

··· /**

Name:1731 birthday cake

How to get:luogu.org

By:Shine_Sky

**/

/***

这道题一看就是用骗分神器--深搜!

我们从下层往上层搜,并且记录上一次的h和r

枚举这一层的h和r 到了最上面一层

判断是否答案合法 如果合法就取最小保存

但是如果不剪枝肯定会T的 所以我们得剪枝

如果只有两重 那么经过测试也是T所以还得一层

就是这三层①要是剩下体积除以最大(虽然取不到)半径所得到的表面积+累计表面积大于答案退出

② 要是剩下来的体积已经小于该层最小体积了就退出

③ 还有 为了剪枝,我们要起先预处理某一层的最大不可的表面积和体积

要注意的是 如果ans没有更新那么就说明不解 可以用flag判断

但是我就不 要是最小面积+当前累计表面积已经比已知答案大了就退出

***/

#include<iostream>
#include<cstdio>
#include<cmath>
#define f(i,a,b)    for(register int i=a;i<=b;++i)
#define fd(i,a,b)    for(register int i=a;i>=b;--i)
using namespace std;
const int N=20000+7;
int ans=987654321,n,m,Minv[N],Mins[N];
inline int read()//读入优化
{
      int num=0;
      char c;
      while(isspace(c=getchar()));
      while(num=num*10+c-48,isdigit(c=getchar()));
      return num;
}
bool flag=1;
inline void dfs(int now,int S,int V,int lasth,int lastr)
{
    if(now==0)//要是已经到了第一层就退出 
    {
        if(V==n)    ans=min(ans,S);//是否为合法答案 
        return;
    }
    //三重恶心的剪枝 
    if(S+2*(n-V)/lastr>ans)    return;
    //要是剩下体积除以最大(虽然取不到)半径所得到的表面积+累计表面积大于答案 退出 
    if(V+Minv[now]>n) return;//要是剩下来的体积已经小于该层最小体积了就退出 
    if(S+Mins[now]>ans)    return;//要是最小面积+当前累计表面积已经比已知答案大了就退出 
    fd(i,lastr-1,now)//从大到小枚举该层半径 
    {
        if(/*flag*/ now==m)    S=i*i;//要是现在是第一层那么就直接加上最小表面积 
    //    flag=0;
        int Maxh=min(lasth-1,(n-V-Minv[now-1])/(i*i));
        fd(j,Maxh,now)//从大到小枚举该层高度 
            dfs(now-1,S+2*i*j,V+i*i*j,j,i);
    }
}
int main()
{
    n=read();m=read();
    f(i,1,m)
        Minv[i]=Minv[i-1]+i*i*i,//cout<<Minv[i]<<endl,
        Mins[i]=Mins[i-1]+2*i*i;//cout<<Mins[i]<<endl;
    int MaxR=sqrt(n);
    dfs(m,0,0,n,MaxR);
    printf("%d",ans==987654321 ? 0 :ans);
    return 0;
}
···