蓝桥杯每日一题2024:DFS暴搜枚举
作者:
荇哩哩
,
2024-03-25 22:06:29
,
所有人可见
,
阅读 52
DFS暴搜枚举
看到数据很小,首先想到暴搜枚举!!!
DFS暴搜枚举:深度优先搜索树是通过递归回溯的方式枚举出所有可能的情况(暴力)
通常适用于数据小的题(一般两位数的数据)且常需要剪枝优化处理
常用于排列型枚举,组合型枚举,指数型枚举等暴力枚举
dfs可能提前退出,所以多组测试点需要初始化!!!
法一:dfs组合型暴搜+剪枝(限制条件)+剪枝优化(除去冗余)
思路:
1.从小到大枚举所有可能的原长len,每一个len用dfs一遍
2.组合型枚举:参数flag用于规定全排列的一种顺序从而转换为组合型
3.返回为true的条件:当前拼好的棍数*len==sum
3.剪枝一:从大到小排序,在相同len下,先取长的木棍递归深度更浅
4.剪枝二:在排序的基础上,如果选了当前长度的木棍后续已经不能返回true,则后续直接跳过与当前一样长的木棍
5.剪枝三:当前第一根小木棍和后面找不到组合凑成len,则len一定不符,返回false(因为要把所有小木棍都选上凑齐数根len长的大木棍)
6.剪枝四:当前最后一根小木棍拼上凑齐len后,后续还不可能则直接返回false
总结:注意dfs递归结束的边界和剪枝
点击查看代码
法一:dfs暴搜+剪枝(限制条件)
思路:
1.由题易知:每一行都得有一个皇后,暴搜依次枚举每一行
2.每一行下枚举每一列,判断列的限制:列限制c,正斜线限制k1,反斜线限制k2(斜线映射:k1=x+y,k2=y-x+n)
总结:注意限制条件
点击查看代码
法一:dfs排列型暴搜+剪枝(限制条件)
思路:
1.排序型暴搜枚举出每一种飞机降落顺序
2.剪枝:根据限制条件,当前飞机的“最晚降落”时刻不能早于上一架“完成降落时刻”
3.贪心:每一架飞机应该尽可能早地开始降落
总结:注意限制条件
点击查看代码