文章目录
三道例题学会DFS剪枝
什么是剪枝
- 其实就是将搜索过程当中一些不必要的部分直接别除掉，因为搜索过程构成了一棵树，别除不必要的部分，就像是在树上将树枝剪掉，故名剪枝。
- 剪枝是回溯法的一种重要优化手段，方法往往先写一个暴力搜索，然后找到某些特殊的数学关系，或者逻辑关系，通过它们的约束让搜索树尽可能浅而小，从而达到降低时间复杂度的目的。
- 一般来说，剪枝的复杂度难以计算。
进入例题提示：如果理解不了的同学建议先看第二部分DFS回溯。
数字王国之军训排队–2942
- 向下递归的搜索过程。这里的剪枝策略是当中间出现不合法的情况就跳过。
- 如果不剪枝就是留到递归出口那去检查，这样做效率是比较慢的。
- 先写一段不剪枝的方法对比一下。
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int a[N],n;
vector<int>v[N];//存放队伍，例：v1就是队伍1中所有成员的 编号，v2是队伍2中所有成员的编号
//搜索，dfs返回在cnt个队伍的情况下能否成功分组
bool dfs(int cnt,int dep)//这里的cnt是队伍的个数
{
if(dep==n+1)//递归出口，每个人都成功分组了
{return true;
//检查当前方案的合法性
for(int i=1;i<=cnt;i++)//对每一个队伍进行检查
{
for(int j=0;j<v[i].size();j++)
{
for(int k=j+1;k<v[i].size();k++)//这两个循环是枚举所有的二元组
{
// if(j==k)continue;//相等，退出,注释掉的原因是k从j+1开始，不会相等
if(v[i][k]%v[i][j]==0)return false;
}
}
}
return true;
}
//枚举每一个所属的队伍
for(int i=1;i<=cnt;i++)
{
v[i].push_back(a[dep]);
if(dfs(cnt,dep+1))return true;//合法
//恢复现场
v[i].pop_back();
}
return false;//不存在
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);//排序是不影响结果的
//枚举这n个队伍，极端情况就是每个人单独成一队
for(int i=1;i<=n;i++)
{
if(dfs(i,1));//在i个队伍的情况下，检查深度为1层，如果当前可以成功分组，那么i就是最小的分组个数
{
cout<<i<<'\n';
break;//找到结果就可以跳出循环了
}
}
return 0;
}
- 接下来看剪枝的写法：
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n;
int a[N];
vector<int> vec[N];//二维vector这样定义，别用vector<vector<int>> vec,因为前者外部vector已声明大小，可以直接调用迭代器，后者不行
bool dfs(int dep,int i)//dep为第几个学生，i为分几队
{//dfs用于判断是否可以分为i队
if(dep==n+1) return true;//如果递归到了最底层，说明可以分成i队
for(int j=0;j<i;j++)//将当前dep学生分到j队
{ bool flag=false;
for(const auto &b:vec[j]) //遍历二维vector，遍历vector用auto枚举比较方便，
{
//这种题型与组合枚举不一样，不要用两条件来思考
if(a[dep]%b==0) //如果当前将要入队的数字学生与队里面的数字可以整除，即有倍数关系
{ //因为用sort排过序，所以a[dep]一定比b大
flag=true;break;
}
}
if(flag) continue;
vec[j].push_back(a[dep]);
if(dfs(dep+1,i)) return true;//布尔dfs的递归这样写，若为false仍需执行后面的恢复现场语句
//恢复现场
vec[j].pop_back();
}
return false; //中间执行完后没有return true，则return false
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)//将1到n队都试试
{
if(dfs(1,i)) //第一个可行的队即为最少的队
{
cout<<i;
break;
}
}
return 0;
}
特殊的三角形–3008
- 解析：
- 具体实现：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
int n;
int st;
int cnt[N];//乘积为i的三元组有多少个
int prefix[N];//定义前缀和数组
//dfs
void dfs(int dep,int st,int mwl,int sum)//sum是前面两条边的和
{
//剪枝
if(mwl>1e6) return ;
if(dep==4)
{
cnt[mwl]++;
return;
}
int up=pow(1e6/mwl,1.0/(3-dep+1))+3;//得到上限
for(int i=st+1;i<(dep==3?sum:up);i++)
{
dfs(dep+1,i,mwl*i,sum+i);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
dfs(1,0,1,0);
for(int i=1;i<=1e6;i++)
{
prefix[i]=prefix[i-1]+cnt[i];
}
int q;cin>>q;
while(q--)
{
int l,r;cin>>l>>r;//输入区间
cout<<prefix[r]-prefix[l-1]<<"\n";
}
return 0;
}
特殊的多边形–3075
和上一题比较像，只需要修改部分内容如下：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int n;
int st;
int cnt[N];//乘积为i的三元组有多少个
int prefix[N];//定义前缀和数组
//dfs
void dfs(int dep,int st,int mwl,int sum)//sum是前面两条边的和
{
//剪枝1
if(mwl>1e5) return ;
if(dep==n+1)
{
cnt[mwl]++;
return;
}
//剪枝2
int up=pow(1e6/mwl,1.0/(n-dep+1))+3;//得到上限
//剪枝3，构造递增
for(int i=st+1;i<(dep==n?min(sum,up):up);i++)//虽然是n边形，但是最后一位的长度依然不能超过sum
{
dfs(dep+1,i,mwl*i,sum+i);
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int q;cin>>q>>n;
dfs(1,0,1,0);
for(int i=1;i<=1e5;i++)
{
prefix[i]=prefix[i-1]+cnt[i];
}
while(q--)
{
int l,r;cin>>l>>r;//输入区间
cout<<prefix[r]-prefix[l-1]<<"\n";
}
return 0;
}
DFS基础回溯
简介
- 回溯法一般使用DFS(深度优先搜索)实现，DFS是一种遍历或搜索图、树或图像等数据结构的算法，当然这个图、树未必要存储下来（隐式处理就是回溯法），常见的是通过某种关系构造出的搜索树，搜索树一般是排列型搜索树（总节点个数一般为n！级别）和子集型搜索树（总节点个数一般为2^n级别)。
- 排列型就是每次枚举选哪个，子集型就是对于每一个元素选或不选（结果与顺序无关）。
- DFS从起始节点开始，沿着一条路径尽可能深入地搜索（一条路走到黑），直到无法继续为止，然后回潮到前一个节点，继续探索其他路径，直到遍历完整个图或树。
- DFS使用栈或递归来管理节点的遍历顺序，一般使用递归。很多时候DFS和回溯法不必过度区分。
- 排列树图解：1~3的全排列
- 子集树
回溯法模版
//求1~n的全排列
int a[N];
bool vis[N];//表示是否被使用过
void dfs(int dep)//dep表示深度
{
//1.首先考虑递归出口的问题
if(dep==n+1)
{
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
cout<<"\n";
return;
}
//2.向下搜索
for(int i=1;i<=n;i++)
{
//2.1先排除不合法的路径
if(vis[i]) continue;//表示i已经被使用过，全排列中1 2 1这种形式不能出现
//2.2修改状态
vis[i]=true;
a[dep]=1;//i可以被使用，并且此时的递归层达到i
//2.3下一层
dfs(dep+1);
//2.4恢复现场
vis[i]=false;
//a[dep]=0可以省略
}
}
例题
N皇后–1508
- 分析
#include<iostream>
using namespace std;
const int N = 12;
int vis[N][N], n, ans;
void dfs(int dep)
{
// 在这个搜索中dep表示行，i表示列
// 1 搜索出口
if(dep == n + 1)
{
ans++;
return;
}
// 2 继续搜索
for(int i = 1; i <= n; ++i)
{
// 2.1 排除非法情况
if(vis[dep][i])
continue;
// 2.2 改变状态
for(int _i = 1; _i <= n; ++_i)
vis[_i][i]++;
for(int _i = dep, _j = i; _i >= 1 && _j >= 1; --_i, --_j)
vis[_i][_j]++;
for(int _i = dep, _j = i; _i <= n && _j >= 1; ++_i, --_j)
vis[_i][_j]++;
for(int _i = dep, _j = i; _i >= 1 && _j <= n; --_i, ++_j)
vis[_i][_j]++;
for(int _i = dep, _j = i; _i <= n && _j <= n; ++_i, ++_j)
vis[_i][_j]++;
// 2.3 下一层
dfs(dep + 1);
// 2.4 还原现场
for(int _i = 1; _i <= n; ++_i)
vis[_i][i]--;
for(int _i = dep, _j = i; _i >= 1 && _j >= 1; --_i, --_j)
vis[_i][_j]--;
for(int _i = dep, _j = i; _i <= n && _j >= 1; ++_i, --_j)
vis[_i][_j]--;
for(int _i = dep, _j = i; _i >= 1 && _j <= n; --_i, ++_j)
vis[_i][_j]--;
for(int _i = dep, _j = i; _i <= n && _j <= n; ++_i, ++_j)
vis[_i][_j]--;
}
}
int main()
{
cin >> n;
dfs(1);
cout << ans << "\n";
return 0;
}
小朋友崇拜圈–182
- 解析
- 代码：
#include<bits/stdc++.h>
using namespace std;
const int N= 1e5 + 10;
int a[N],dfn[N];
int n,idx,mindfn;
int dfs(int b)
{
dfn[b]=++idx;//时间戳
if(dfn[a[b]]==0) return dfs(a[b]);//要有return ，若时间戳为空，继续递归
else//有时间戳的情况
{
if(dfn[a[b]]>=mindfn) return dfn[b]-dfn[a[b]]+1;//下一个崇拜对象大于等于最小时间戳，说明闭环
return 0;//下一个崇拜对象小于最小时间戳，说明不闭环
}
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int maxs=0;
for(int i=1;i<=n;i++) //从dfn为空的开始递归
{
if(dfn[i]==0)
{
mindfn=idx+1;//更新最小时间戳
maxs=max(dfs(i),maxs);//取所有环中的最大值
}
}
cout<<maxs<<endl;
return 0;
}
- 第二种形式–dfs中有一点点不同
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
int n,a[N],dfn[N],mindfn;
int idx;//这是一个正在变化的数字，表示此时的时间
int ans;
int dfs(int x)
{
dfn[x]=++idx;
//递归出口
if(dfn[a[x]])
{
if(dfn[a[x]]>=mindfn)
return dfn[x]-dfn[a[x]]+1;
return 0;
}
return dfs(a[x]);
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
mindfn=idx+1;//更新
ans=max(ans,dfs(i));
}
}
cout<<ans<<endl;
}
全球变暖–178
- 分析：
- 代码：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+5;
int n;
char mp[N][N];
int scc,col[N][N];
int dx[]={0,0,1,-1};//表示四个方向的偏移量
int dy[]={1,-1,0,0};
bool vis[N*N];//表示某种颜色是否剩下来
void dfs(int x,int y)
{
col[x][y]=scc;
for(int i=0;i<4;i++)//i往四个方向走
{
int nx=x+dx[i];//下一个x的位置
int ny=y+dy[i];
if(col[nx][ny]||mp[nx][ny]=='.')continue;//海洋！不要过去
// 第一个条件是说：如果已经有颜色了就不要再走，否则会造成两个点反复横跳
dfs(nx,ny);//因为题干中保证了边缘是海洋，所以不用判断了
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>mp[i]+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(col[i][j]||mp[i][j]=='.')continue;//如果是海洋，跳过
scc++;//当前的颜色编号加1
dfs(i,j);
}
}
//进行淹没
int ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mp[i][j]=='.')continue;//特判，防止超出地图
bool tag=true;//默认颜色会剩下来（四个方向都有陆地）
for(int k=0;k<4;k++)//往四个方向走
{
int x=i+dx[k];
int y=j+dy[k];
if(mp[x][y]=='.')tag=false;
}
if(tag)
{
if(!vis[col[i][j]])ans++;//如果这个颜色没有出现过，答案++
vis[col[i][j]]=true;
}
}
}
cout<<scc-ans<<endl;
return 0;
}
记忆化搜索
简介
- 就是将搜索过程中会重复计算且结果相同的部分保存下来，作为一个状态，下次访问到这个状态时直接将这个子搜索的结果返回，而不需要再重新算一遍。
- 通常会使用数组或map来进行记忆化，下标一般和dfs的参数表对应。
- 注意使用记忆化需要保证重复计算的结果是相同的，否则可能产生数据失真。
斐波那契数列
如果直接采用递归来做，时间复杂度将接近O(2^),但是我们会发现有大部分的重复计算，比如F[n- 2]在求F[n]的时候算过，在求F[n-1]的时候又被算了一次，而F[1]计算次数更多了，但它们在重复的时候的结果是相同的，所以可以采用记忆化（也叫带备忘录的搜索）。
- 如果采用原来的方法：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll p=1e9+7;
const int inf=1e9,N=1e3+3;
ll f(int n)
{
if(n<=2)return 1;
else
return (f(n-1)+f(n-2))%p;
}
int main()
{
int n;cin>>n;
cout<<f(n)<<endl;
return 0;
}
可以发现，当输入值为50的时候计算就非常慢了。
- 增加备忘录：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll p=1e9+7;
const int inf=1e9,N=1e5+3;
ll dp[N];
ll f(int n)
{
if(n<=2)return 1;
if(dp[n]!=-1)return dp[n];//被算过才能直接返回
else
return dp[n]=(f(n-1)+f(n-2))%p;
}
int main()
{
memset(dp,-1,sizeof dp);//初始化dp数组 ，dp为-1代表还没有被算过
int n;cin>>n;
cout<<f(n)<<endl;
return 0;
}
这下输入5000也可以直接算出来啦。
- 之前的文章中提到过memset函数，这里再次说一下用法:
C++中的memset函数用于将一段内存区域的内容设置为指定的值。它的原型如下：
cpp
复制代码运行
void* memset(void* ptr, int value, size_t num);
参数说明：
ptr：指向要填充的内存区域的指针。
value：要设置的值，以int形式给出，但实际上是按unsigned char类型处理的。
num：要设置的字节数。
返回值：返回指向填充后的内存区域的指针。
混境之地5-3820
- 未加记忆化搜索：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+3;
int n,m,k;//起点，终点和高度
int sx,sy,fx,fy;
int h[N][N];//高度数组
int dx[]={0,0,1,-1};//表示四个方向的偏移量
int dy[]={1,-1,0,0};
bool inmap(int x,int y)//判断是否在地图之中
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
//返回值表示能否到达终点（fx，fy）
bool dfs(int x,int y,int t)//t表示当前使用的喷气背包的次数
{
if(x==fx&&y==fy)return true;//到达终点
for(int i=0;i<4;i++)
{
int nx=x+dx[i];//下一个方向
int ny=y+dy[i];
if(!inmap(nx,ny))continue;//不在地图内，返回
if(!t)//没用过背包
{
//不用
if(h[x][y]>h[nx][ny]&&dfs(nx,ny,0))return true;
//用
if(h[x][y]+k>h[nx][ny]&&dfs(nx,ny,1))return true;
}
else
{
//只能不用
if(h[x][y]>h[nx][ny]&&dfs(nx,ny,1))return true;
}
}
return false;
}
int main()
{
//控制输入
cin>>n>>m>>k;
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>h[i][j];
}
}
cout<<(dfs(sx,sy,0)?"Yes":"No")<<endl;
return 0;
}
- 加上记忆化搜索：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+3;
int n,m,k;//起点，终点和高度
int sx,sy,fx,fy;
int h[N][N];//高度数组
int dx[]={0,0,1,-1};//表示四个方向的偏移量
int dy[]={1,-1,0,0};
int dp[N][N][2];//这里不能用bool
bool inmap(int x,int y)//判断是否在地图之中
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
//返回值表示能否到达终点（fx，fy）
bool dfs(int x,int y,int t)//t表示当前使用的喷气背包的次数
{
if(x==fx&&y==fy)return true;//到达终点
if(dp[x][y][t]!=-1)return dp[x][y][t];
for(int i=0;i<4;i++)
{
int nx=x+dx[i];//下一个方向
int ny=y+dy[i];
if(!inmap(nx,ny))continue;//不在地图内，返回
if(!t)//没用过背包
{
//不用
if(h[x][y]>h[nx][ny]&&dfs(nx,ny,0))return dp[x][y][t]=true;
//用
if(h[x][y]+k>h[nx][ny]&&dfs(nx,ny,1))return dp[x][y][t]=true;
}
else
{
//只能不用
if(h[x][y]>h[nx][ny]&&dfs(nx,ny,1))return dp[x][y][t]=true;
}
}
return dp[x][y][t]=false;
}
int main()
{
memset(dp,-1,sizeof dp);
//控制输入
cin>>n>>m>>k;
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>h[i][j];
}
}
cout<<(dfs(sx,sy,0)?"Yes":"No")<<endl;
return 0;
}
地宫取宝-216
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll p=1e9+7;
const int N=55;
int n,m,k;//起点，终点和高度
int c[N][N];//高度数组
int dx[]={0,1};//表示四个方向的偏移量
int dy[]={1,0};
int dp[N][N][15][15];//这里不能用bool
bool inmap(int x,int y)//判断是否在地图之中
{
return 1<=x&&x<=n&&1<=y&&y<=m;
}
//表示从（1,1）到（x，y），有cnt件宝贝，且最大值为mx的方案数
ll dfs(int x,int y,int mx,int cnt)//t表示当前使用的喷气背包的次数
{
if(x==n&&y==m)return (ll)(cnt==k);//到达终点
if(dp[x][y][mx][cnt]!=-1)return dp[x][y][mx][cnt];
ll res=0;//方案数
for(int i=0;i<2;i++)
{
int nx=x+dx[i];//下一个方向
int ny=y+dy[i];
if(!inmap(nx,ny))continue;//不在地图内，返回
//拿这个宝贝
if(c[nx][ny]>mx&&cnt<k) res=(res+dfs(nx,ny,c[nx][ny],cnt+1))%p;
//不拿这个宝贝
res=(res+dfs(nx,ny,mx,cnt))%p;
}
return dp[x][y][mx][cnt]=res;
}
int main()
{
memset(dp,-1,sizeof dp);
//控制输入
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>c[i][j];
c[i][j]++;
}
}
cout<<(dfs(1,1,0,0)+dfs(1,1,c[1][1],1))%p;//不拿和拿了
return 0;
}