AcWing168 生日蛋糕 dfs 剪枝

本文主要是介绍AcWing168 生日蛋糕 dfs 剪枝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

AcWing 168 生日蛋糕 dfs 剪枝

原题链接(https://www.acwing.com/problem/content/description/170/)

思路：

要求最小的表面积，可知上表面总面积等于最底层蛋糕的上表面面积，那么就只需要求侧面积的最小值。预处理s的最小值时，将蛋糕从上往下，h,r都为1开始，往下面依次递增。
由于每一层与dep,s,v,r,h,R[dep+1],H[dep+1]有关，那么每一层都是一个状态，所以采用dfs。
搜索到dep层时，本层蛋糕的s与v由r和h求得。因为从下往上，r的下界为dep,因为这是预处理时满足最小值的s。上界：由蛋糕满足高度和半径单调递减，那么r<=R[dep+1]-1，另一方面，那么又因为每一层蛋糕的体积满足PIRRH=PI(N-V),
当H=1时，R最大为sqrt(N-V).
所以r的范围为[dep,min(sqrt(N-V),R[dep+1]-1)]
同理的h的范围为[dep,min((N-V)/r*r,H[dep+1]-1)]

剪枝：
1,s: 当前s加上预处理的本层最小的s之后大于了ans，return
2.v:当前v加上预处理的本层最小的v之后大于了N,return
3.S = sum(2RiHi)，V = sum(RiRiHi)，则S = sum(2RiHiRk+1 / Rk+1) > 1 / Rk+1 * sum(2RiRiHi ) = 2 / Rk+1 * sum(RiRiHi) = 2V / Rk+1，所以当2*(N-V)/R[dep] + s > ans时，continue;

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int H[25],R[25],mins[25],minv[25],n,m,ans=INF;
void dfs(int dep,int v, int s){//dfs变量：dep,s,v 剪枝：s,v,s与v的关系,dep  //剪枝 if(s+mins[dep]>ans) return;//面积：已经不是最优的 if(v+minv[dep]>n) return;//体积 ：已经超过了规定的体积 if(2*(n-v)/R[dep+1]+s>ans) return;//面积与体积的关系推出的奇奇怪怪的剪枝策略 if(dep==0){//递归边界 if(v==n) ans=min(ans,s);//如果同时还满足v==n，那么更新ans return;} for(int r=min((int)sqrt(n-v),R[dep+1]-1);r>=dep;r--){//下界：dep,上界:min(首先满足从下往上单调递减，所以满足R[dep+1]-1,又根据公式PI*r*r*h=PI*(N-v) for(int h=min((n-v)/(r*r),H[dep+1]-1);h>=dep;h--){int t=0;if(dep==m) t=r*r;//最下面那层，也是开始搜索的第一层，加上整体的上表面的面积 R[dep]=r,H[dep]=h;//更新r和dep dfs(dep-1,v+r*r*h,s+2*r*h+t);//往下一层搜素 }}
}
int main(){for(int i=1;i<=20;i++){//预处理出最小的，当从上往下r,h,同时为1，2，3这样递增时，显然满足smin mins[i]=mins[i-1]+2*i*i;//s=2*PI*r*h,此时默认r,h相同且从1开始递增 minv[i]=minv[i-1]+i*i*i;}scanf("%d%d",&n,&m);H[m+1]=R[m+1]=INF;//设置边界 dfs(m,0,0);//从最下面一层开始dfs if(ans==INF) puts("0");else printf("%d\n",ans);return 0;
}