每日一题 day53 打卡
Analysis
观察一个蛋糕的俯视图，上表面的面积其实就是最下面那一层的底面积，所以在第一次搜索的时候加入这个底面积，之后就只用考虑侧面积就好啦.
就是每次枚举r和h，如何选取上下界呢？
将上一层的高度记作lh，上一层的半径记作lr，则上界很好判断，就是lh−1和lr−1，
底层应该是选取三次根号下20000约为28的范围
现在考虑下界：
自然选取1是会T得很惨的，下界就是最小值嘛，最上面一层的r和h的最小值都是1啊，那还有几层下界就是几啦！
然后来愉快地剪枝：
比较好想的剪枝是这两个：
当当前的面积总和已经超过之前的答案时，return
当当前体积超过了要求的体积时，return
还有一些剪枝，思维难度也不算高：
当现在的已有体积加上之后的最大
（并不是真正的最大，会比最大还要大一些）体还要小于要求的体积时，return当当前的已有面积加上之后的最小
（自然也是比真正的最小还要小一些）面积比已有答案还要大时，return
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define INF 2147483647
#define rep(i,s,e) for(register int i=s;i<=e;++i)
#define dwn(i,s,e) for(register int i=s;i>=e;--i)
using namespace std;
inline int read()
{
int x=,f=;
char c=getchar();
while(c<''||c>'') {if(c=='-') f=-; c=getchar();}
while(c>=''&&c<='') {x=x*+c-''; c=getchar();}
return f*x;
}
inline void write(int x)
{
if(x<) {putchar('-'); x=-x;}
if(x>) write(x/);
putchar(x%+'');
}
int n,m,ans=INF;
void dfs(int layer,int volume,int area,int radius,int height)
{
if(area>=ans) return;
if(layer==m+&&volume==n)
{
ans=min(ans,area);
return;
}
if(volume>=n) return;
int now_layer=m-layer+;
if(volume+now_layer*radius*radius*height<n) return;
if(area+now_layer*>ans) return;
if(layer==)
{
rep(r,m,radius)
rep(h,m,height)
dfs(layer+,volume+r*r*h,area+*r*h+r*r,r,h);
}
else
{
rep(r,now_layer,radius-)
rep(h,now_layer,height-)
dfs(layer+,volume+r*r*h,area+*r*h,r,h);
}
}
signed main()
{
n=read();m=read();
dfs(,,,,);
if(ans==INF) write();
else write(ans);
return ;
}
请各位大佬斧正（反正我不认识斧正是什么意思）