下载安装百度地图导航,昆明网站优化建设,网站免费申请注册,电商小程序开发需要多少钱定义#xff1a;
剪枝#xff0c;就是减少搜索树的规模、尽早排除搜索树中不必要分支的一种手段。 在深度优先搜索中#xff0c;有以下几类常见的剪枝方法:
优化搜索顺序排除等效冗余可行性剪枝最优性剪枝记忆化剪枝
例题1#xff1a;AcWing 167.木棒
题目#xff1a;…定义
剪枝就是减少搜索树的规模、尽早排除搜索树中不必要分支的一种手段。 在深度优先搜索中有以下几类常见的剪枝方法:
优化搜索顺序排除等效冗余可行性剪枝最优性剪枝记忆化剪枝
例题1AcWing 167.木棒
题目
https://www.acwing.com/problem/content/169/ 将一组等长的木棒随机砍断得到若干小木棍计算初始木棒的最小长度
思路
首先从小到达枚举原木棒长度len最小的是最大小木棍长度木棍总和sum满足sum%len0根数就是sum/len。如果直接这样暴搜的话会时间超限所以需要剪枝优化。 1.优化搜索顺序把木棍长度从大到小排序优先尝试较长木棍。 2.排除等效冗余 1 限制先后加入一根原始木棒的木棍长度是递减的。因为先拼x再拼y和先拼y再拼x是等效的。 2 对于当前原始木棒记录最近一次尝试拼接木棒的长度。如果搜索失败直接返回false 3 如果当前原始木棒中尝试拼入的第一根木棍的递归分支就返回失败那直接判定失败 4 如果在当前原始木棒中拼入一根木棍后木棒恰好被拼接完整并且接下来拼接剩余木棒的递归分支返回失败直接返回失败。
AC代码
#includebits/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(stickcnt)return true;if(cablen) return dfs(stick1,0,1);int falg0;//剪枝(2) for(int ilast;in;i){if(!v[i] caba[i]len falg!a[i]){v[i]1;if(dfs(stick,caba[i],i1))return true;falga[i];v[i]0;//还原现场if(cab0 || caba[i]len)//剪枝(3)(4) return false; }}return false;//所有分支都尝试过搜索失败
}signed main()
{IOSwhile(cinn n){int sum0, val0;for(int i1; in; i){cina[i];suma[i];valmax(val,a[i]);}sort(a1,an1);reverse(a1,an1);for(lenval;lensum;len){if(sum%len) continue;cntsum/len;//原始木棒长度为len共cnt根 memset(v,0,sizeof(v));if(dfs(1,0,1)) break;}coutlen\n;}return 0;
}例题2AcWing 168.生日蛋糕
题目
https://www.acwing.com/problem/content/170/ 一个生日蛋糕每层都是一个圆柱体给出体积和层数找出最小表面积
思路
从下往上搜索枚举每层的半径和高度作为分支。整个蛋糕的上表面面积之和等于最底层的圆面积可以在第m层直接累加到s中这样在第m-1层搜索中值需要计算侧面积。 剪枝 1.在第u层只需枚举范围内的半径和高度即可 首先r属于[u,min(sqrt(n-v),r[u1]-1)]h属于[u,min(sqrt(n-v)/r*r,h[u1]-1)]. 2.在确定范围中使用倒序枚举。 3.预处理出从上往下前i层的最小体积和侧面积。当1~i层的半径分别取1,2,3……i高度也分别取1,2,3……i有最小体积和侧面积。如果当前体积v加上前几层的最小体积大于n剪枝。 4.如果当前表面积s加上前几层的最小侧面积大于已经搜到的答案剪枝。 5.比较难敲看图片。图片中的dep等价于上面的u。
AC代码
#includebits/stdc.h
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;const int N25,INT1e9;
int n,m,r[N],h[N],a[N],b[N],ansINT;void dfs(int u,int v,int s)
{if(va[u]n) return;if(sb[u]ans) return;if(s2*(n-v)/r[u1]ans) return;if(!u){if(vn)anss;return;}for(int r1min(r[u1]-1,(int)sqrt(n-v));r1u;r1--)for(int h1min(h[u1]-1,(n-v)/r1/r1);h1u;h1--){int t0;if(um)tr1*r1;r[u]r1,h[u]h1;dfs(u-1,vr1*r1*h1,s2*r1*h1t);}
}signed main()
{IOScinnm;for(int i1;im;i){a[i]a[i-1]i*i*i;b[i]b[i-1]2*i*i;}r[m1]h[m1]INT;dfs(m,0,0);if(ansINT) ans0;coutans\n;return 0;
}
