AcWing 168. 搜索剪枝
原题链接
中等
作者:
想养一只皮卡丘
,
2020-11-14 18:15:26
,
所有人可见
,
阅读 382
#include<bits/stdc++.h>
using namespace std;
const int max1=0x3f3f3f3f;
int n,m;
int minv[22], mins[22], ans=max1;
int h[22],r[22], s=0,v=0;//当前表面积为s,体积为v
void dfs(int dep){
//处理边界
if(!dep)
{
if (v==n) ans=min(ans,s);
return;
}
//上下边界剪枝
for(r[dep]=min((int)sqrt(n-v),r[dep+1]-1);r[dep]>=dep;r[dep]--)
for(h[dep]=min((int)((double)(n-v)/(r[dep]*r[dep])), h[dep+1]-1); h[dep]>=dep;h[dep]--)
{
//可行性剪枝
if(v+minv[dep-1]>n) continue;
//最优化剪枝一
if(s+mins[dep-1]>=ans) continue;
//最优化剪枝二(未来最少花费代价)
if(s+(double)2*(n-v)/r[dep]>ans) continue;
if (dep == m) s+=r[dep]*r[dep]; //所有层的裸露的部分的面积
s+=2*r[dep]*h[dep]; //s=2rh
v+=r[dep]*r[dep]*h[dep]; //v=rrh
dfs(dep-1); //从下往上搜(优化搜索顺序剪枝)
if(dep == m) s-=r[dep]*r[dep]; //还原现场
s-=2*r[dep]*h[dep];
v-=r[dep]*r[dep]*h[dep];
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;++i)//剪枝1:预处理最小的体积和表面积
{
minv[i]=minv[i-1]+i*i*i;
mins[i]=mins[i-1]+i*i;
}
h[m+1]=r[m+1]=max1;
dfs(m); //从下往上搜(优化搜索顺序剪枝)
if(ans==max1)
cout<<0;
else
cout<<ans;
}