题目链接
https://www.luogu.org/problemnew/show/P1731
分析
这题真 [哔] 恶心, 加了一堆奇奇怪怪的优化
首先明确一点, 半径和高都必须是正整数, 意味着它们最小为 \(1\)
同时我们通过数学公式可以推得: 当剩下体积 \(v\)一定时, 层数越少面积越小, 也就是说, 越趋进一个圆柱面积越小.
于是我们可以预处理出搜索到每一层的最小剩余体积 \(miv[i]=miv[i-1]+i^3\)
假设我们从下 (第 m 层) 往上 (第 1 层) 枚举
那么我们可以列出优化:
设定初始 \(r?\)范围为 \([1,\sqrt{n/m}]?\),\(h?\)范围 \([1,n/(m * m)]?\)
同时在 \(DFS\)过程中我们枚举 \(r\)从上次 \(DFS\)的 \(pre_r-1\)递减到现在搜索的层数 \(now\), 再枚举 \(h\), 则其上限为 \(min((left-miv[now-1])/(r * r),pre_h-1)\),\(left\)是还剩下的体积, 而下限也为 \(now\)
同时还有剪枝
我们可以通过剩余体积 \(left\)预估出接下来面积最小值 (虽然可能并不能达到) 为 \(left * 2/pre_r\), 如果预估最小值加上当前面积累计值已大于已有的答案, 则直接返回;
同时相对于体积, 我们已经预处理出每一层最小剩余体积, 如果 \(miv[now]>left\)则直接返回
代码
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <algorithm>
- #include <cctype>
- #include <queue>
- #include <cmath>
- #define ll long long
- #define ri register int
- using std::min;
- using std::sqrt;
- using std::max;
- template <class T>inline void read(T &x){
- x=0;int ne=0;char c;
- while(!isdigit(c=getchar()))ne=c=='-';
- x=c-48;
- while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
- x=ne?-x:x;return ;
- }
- const int maxn=17;
- const int inf=0x7fffffff;
- int n,m,ans=inf,tmp;
- int miv[maxn];
- void dfs(int now,int val,int left,int r,int h){
- if(!now){
- if(!left)ans=min(ans,val);
- return;
- }
- if(now<=0||left<=0)return ;
- if(val+(left<<1)/r>ans||miv[now]>left)return;
- for(ri i=r-1;i>=now;i--){
- if(now==m)val=i*i;
- tmp=min(left-miv[now-1]/(i*i),h-1);
- for(ri j=tmp;j>=now;j--){
- dfs(now-1,val+2*i*j,left-i*i*j,i,j);
- }
- }
- return;
- }
- int main(){
- read(n),read(m);
- for(ri i=1;i<=m;i++)miv[i]=miv[i-1]+i*i*i;
- int r=(int)sqrt(n/m),h=n/(m*m);
- dfs(m,0,n,r,h);
- if(ans==inf)puts("0");
- else printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2767963.html