搜索（剪枝）

定义：

剪枝，就是减少搜索树的规模、尽早排除搜索树中不必要分支的一种手段。
在深度优先搜索中，有以下几类常见的剪枝方法:

• 优化搜索顺序
• 排除等效冗余
• 可行性剪枝
• 最优性剪枝
• 记忆化剪枝

例题1：AcWing 167.木棒

题目：

https://www.acwing.com/problem/content/169/
将一组等长的木棒随机砍断，得到若干小木棍，计算初始木棒的最小长度

思路：

首先从小到达枚举原木棒长度len，最小的是最大小木棍长度，木棍总和sum满足sum%len==0，根数就是sum/len。如果直接这样暴搜的话会时间超限，所以需要剪枝优化。
1.优化搜索顺序：把木棍长度从大到小排序，优先尝试较长木棍。
2.排除等效冗余：
（1） 限制先后加入一根原始木棒的木棍长度是递减的。因为先拼x再拼y和先拼y再拼x是等效的。
（2） 对于当前原始木棒，记录最近一次尝试拼接木棒的长度。如果搜索失败直接返回false
（3） 如果当前原始木棒中尝试拼入的第一根木棍的递归分支就返回失败，那直接判定失败
（4） 如果在当前原始木棒中拼入一根木棍后，木棒恰好被拼接完整，并且接下来拼接剩余木棒的递归分支返回失败，直接返回失败。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int a[70],v[70],n,len,cnt;bool dfs(int stick, int cab, int last)
{if(stick>cnt)return true;if(cab==len) return dfs(stick+1,0,1);int falg=0;//剪枝(2) for(int i=last;i<=n;i++){if(!v[i] && cab+a[i]<=len && falg!=a[i]){v[i]=1;if(dfs(stick,cab+a[i],i+1))return true;falg=a[i];v[i]=0;//还原现场if(cab==0 || cab+a[i]==len)//剪枝(3)(4) return false; }}return false;//所有分支都尝试过，搜索失败 
}signed main()
{IOSwhile(cin>>n && n){int sum=0, val=0;for(int i=1; i<=n; i++){cin>>a[i];sum+=a[i];val=max(val,a[i]);}sort(a+1,a+n+1);reverse(a+1,a+n+1);for(len=val;len<=sum;len++){if(sum%len) continue;cnt=sum/len;//原始木棒长度为len，共cnt根 memset(v,0,sizeof(v));if(dfs(1,0,1)) break;}cout<<len<<'\n';}return 0;
}

例题2：AcWing 168.生日蛋糕

题目：

https://www.acwing.com/problem/content/170/
一个生日蛋糕，每层都是一个圆柱体，给出体积和层数，找出最小表面积

思路：

从下往上搜索，枚举每层的半径和高度作为分支。整个蛋糕的上表面面积之和等于最底层的圆面积，可以在第m层直接累加到s中，这样在第m-1层搜索中，值需要计算侧面积。
剪枝：
1.在第u层，只需枚举范围内的半径和高度即可
首先，r属于[u,min(sqrt(n-v),r[u+1]-1)]；h属于[u,min(sqrt(n-v)/r*r,h[u+1]-1)].
2.在确定范围中，使用倒序枚举。
3.预处理出从上往下前i层的最小体积和侧面积。当1~i层的半径分别取1,2,3……i，高度也分别取1,2,3……i，有最小体积和侧面积。如果当前体积v加上前几层的最小体积大于n，剪枝。
4.如果当前表面积s加上前几层的最小侧面积大于已经搜到的答案，剪枝。
5.比较难敲，看图片。图片中的dep等价于上面的u。

AC代码：

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N=25,INT=1e9;
int n,m,r[N],h[N],a[N],b[N],ans=INT;void dfs(int u,int v,int s)
{if(v+a[u]>n) return;if(s+b[u]>=ans) return;if(s+2*(n-v)/r[u+1]>=ans) return;if(!u){if(v==n)ans=s;return;}for(int r1=min(r[u+1]-1,(int)sqrt(n-v));r1>=u;r1--)for(int h1=min(h[u+1]-1,(n-v)/r1/r1);h1>=u;h1--){int t=0;if(u==m)t=r1*r1;r[u]=r1,h[u]=h1;dfs(u-1,v+r1*r1*h1,s+2*r1*h1+t);}
}signed main()
{IOScin>>n>>m;for(int i=1;i<=m;i++){a[i]=a[i-1]+i*i*i;b[i]=b[i-1]+2*i*i;}r[m+1]=h[m+1]=INT;dfs(m,0,0);if(ans==INT) ans=0;cout<<ans<<'\n';return 0;
}