从玄学剪枝到理论深搜——P1731 生日蛋糕
HYLW
·
·
算法·理论
前言
DFS，俗称深搜，但是众所周知，在某些“玄学”剪枝优化的辅助下，DFS可以媲美BFS，并且由于其简单的基础思路搭建和优美的暴力美感，是十分令人上头的，唯一的难点在于“剪什么枝？”“如何剪枝？”
剪枝优化常用方向
一般情况下，应当 \bold{优先搜索分支节点少的节点}。
我们知道，DFS 是以递归的形式呈现的，那么这就涉及到爆栈的问题，优先搜索分支节点少的节点可能更快的得到\bold{可行性答案}。
应当 \bold{避免搜索到同等效果的情况} 。
- **最优性剪枝**
$\bold{当当前节点向下搜索一定不能使方案比已有方案更优时，不再搜索}$。
- **记忆化搜索（DP）**
字面意思。
- **状态压缩**
以二进制压缩为代表，
# 例题展示
[$\bold{luogu P1731 生日蛋糕}$](https://www.luogu.com.cn/problem/P1731)
# [NOI1999] 生日蛋糕
- ## 题目背景
[数据加强版 link](https://www.luogu.com.cn/problem/T148457)
- ## 题目描述
7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $N\pi$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。
设从下往上数第 $i$（$1 \leq i \leq M$）层蛋糕是半径为 $R_i$，高度为 $H_i$ 的圆柱。当 $i \lt M$ 时，要求 $R_i \gt R_{i+1}$ 且 $H_i \gt H_{i+1}$。
由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积 $Q$ 最小。
请编程对给出的 $N$ 和 $M$，找出蛋糕的制作方案（适当的 $R_i$ 和 $H_i$ 的值），使 $S=\dfrac{Q}{\pi}$ 最小。
（除 $Q$ 外，以上所有数据皆为正整数）
- ## 输入格式
第一行为一个整数 $N$（$N \leq 2 \times 10^4$），表示待制作的蛋糕的体积为 $N\pi$。
第二行为 $M$（$M \leq 15$），表示蛋糕的层数为 $M$。
- ## 输出格式
输出一个整数 $S$，若无解，输出 $0$。
- ## 样例 #1
- ### 样例输入 #1
```
100
2
```
- ### 样例输出 #1
```
68
```
# 思路及正文
首先，确定优化方式——根据**题目性质**，找出特殊、隐藏的优化方位，结合**联想**、**猜想**，并证明，来优化。
>首先，我们需要采取最朴素的方式，把我们的基础思路搭建出来。
显然，我们知道其每一层蛋糕的半径与高是自下而上单调递减的，并且，半径与高都为正整数，这意味着，我们可以逐一枚举每一层的半径与高，去寻找答案，即，**本质上去枚举高与半径**。
>接着，确定枚举（爆搜）顺序，在这个过程中，我们便可以通过调整顺序来实现优化
那么，我们遇到的第一个问题，便是，从上向下搜，还是从下向上搜？
显然，我们应当从下向上搜，因为最下面一层的体积与表面积一定是最大的，当一个空间只有很少的剩余时，我们可能的方案更少。
>>优先搜索分支节点少的节点
其次，每一层有两个变量需要枚举，即半径与高，那么我们该如何枚举？
那么，我们知道，在所有的半径与高接近的极限情况下（这显然不合法）（根据题意忽略 $\pi$）
$$N=M\cdot R^2\cdot H（限制条件）$$
$$S= M\cdot 2R\cdot H+R^2（所求目标）$$
显然我们的枚举遵循限制条件的性质，由于半径为平方级别，所以我们以半径为基点，用半径限制枚举高，来枚举。
>> 观察题目性质
说到限制，根据“每一层蛋糕的半径与高是自下而上单调递减的”，那么第一层的半径和高必大于等于 $1$ ,第二层大于等于 $2$ ，即 $i\leq R_i,H_i $ ，这是一个优化点，而根据上面的极限方程
$$H=1,R_{max}\leq \sqrt{\frac{N}{M}}$$
$$H_{max}\leq \frac{N}{M\cdot R^2}$$
那么我们设 $V$ 表示枚举过的层的总体积，那么我们就可以得到每一层的限制，
$$R_i\leq \sqrt{\frac{N-V}{M-i+1}}$$
$$H_i\leq \frac{N-V}{(M-i+1)\cdot R^2}$$
由于满足单调递减的性质，所以我们取一个最小值，最终的区间为
$$i \leq R_i\leq \min(\sqrt{\frac{N-V}{M-i+1}},R_{i-1}),i\leq H_i \leq \min(\frac{N-V}{(M-i+1)\cdot R^2},H_{i-1})$$
与上面一样，我们从较大值搜到较小值。
>>题目性质
然后根据上面的结论，我们可以得到每一层的最小体积与最小表面积，即
$$V_{min-u}=\sum\limits_{i=1}^{u}i^3(R_i=i,H_i=i)$$
$$S_{min-u}=\sum\limits_{i=1}^{u}2i^2(R_i=i,H_i=i)$$
这样的方案不一定合法，但是可以作为一个底线，即当 $N\leq V+V_{min-u}$ ，无需再搜；当 $ans\leq S+S_{min-u}$ 时，无需再搜。
>>题目性质
最后，我们还需要更进一步，观察到
$$N=\sum\limits_{i=1}^{M}R_i^2\cdot H_i$$
$$S=\sum\limits_{i=1}^{M} 2R_i\cdot H_i=\frac{2}{R_{max}}\sum\limits_{i=1}^{M} R_i\cdot R_{max} H_i \geq \frac{2}{R_{max}}\sum\limits_{i=1}^{M} R_i^2 H_i $$
即得
$$S\geq \frac{2}{R_{max}}N$$
这便是最接近、高效的剪枝，因为在这个式子中 $S$ 与 $N$ 是最贴切的，推广到每一层即为（从上到下 $1$~$i$）
$$N-V=N_{u-M}=\sum\limits_{i=1}^{u}R_i^2\cdot H_i$$
$$S_{u-M}\geq \frac{2}{R_{max}}\sum\limits_{i=1}^{u} R_i^2 H_i $$
那么当 $S+\frac{2}{R_{u+1}}(N-V)\geq ans$ 时，无需再搜。
剪枝毕。
# 样例代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int M = 22,INF = 0X3F3F3F3F;
int mins[M],minv[M];
int n,m;
int r[M],h[M];
int ans=INF;
void dfs(int u,int v,int s){
if(v+minv[u]>n) return ;
if(s+mins[u]>=ans) return ;
if(s+2/r[u+1]*(n-v)>=ans) return ;
if(!u){
if(v==n) ans=s;
return ;
}
for(int i=min(r[u+1]-1,(int)sqrt(n-v));i>=u;i--)
for(int j=min(h[u+1]-1,(n-v)/i/i);j>=u;j--){
int t=0;
if(u==m) t=i*i;
r[u]=i;h[u]=j;
dfs(u-1,v+i*i*j,s+2*i*j+t);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
mins[i]=mins[i-1]+2*i*i;
minv[i]=minv[i-1]+i*i*i;
}
r[m+1]=h[m+1]=INF;
dfs(m,0,0);
printf("%d",ans);
return 0;
}
```