我们知道不管是内部搜索还是外部搜索都可以形成一棵搜索树如果将搜索树全部遍历一遍效率会很低但如果我们能在搜索的过程中提前预知判断某一些不可能是正确答案的情况就可以不用遍历其下的子树从而提高我们的算法效率

优化搜索顺序

尽量保证不搜索重复的状态就是在不考虑顺序时采用组合的方式搜索可行性剪枝

不合法提前退出最优性剪枝

如果当前答案无论如何都比目前的最优解要差那就可以不要往下搜了记忆化搜索DP

小猫爬山

经历了千辛万苦小猫们终于爬上了山顶但是疲倦的它们再也不想徒步走下山了呜咕_。

每租用一辆缆车翰翰和达达就要付

优化搜索顺序比较一只比较轻的猫和另一只比较重的猫显然是比较重的猫带来的分支数量较少因为如果猫非常重可以直接把车占满但是猫很轻的话我们就要考虑还要加什么别的猫因此将所有猫按从大到小排序优先放重猫可行性剪枝当发现目前小猫的重量已经超过缆车承重就不要再往下搜了最优性剪枝当发现目前缆车数量已经大于等于当前计算出的缆车最少数量就不要再搜索了

#include

{ios::sync_with_stdio(false);cin.tie(0),

cout.tie(0);cin

4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......

......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.

end输出样例

417369825632158947958724316825437169791586432346912758289643571573291684164875293

416837529982465371735129468571298643293746185864351297647913852359682714128574936题意

先做一个小优化看比如说一个3x3小方格中有哪些数字没被用过随意选择一个格子然后对这些数字依次枚举搜索即可

优化搜索顺序选择格子时尽量选择分支数量较少的格子比如说一个格子有2种填法另一个格子有5种那肯定优先选择2种的可行性剪枝一旦与行列九宫格重复时就不要继续搜了位运算优化

比如0

我们考虑这一位上能不能填这个数时应该考虑二进制数的交集即在行、列、九宫格的二进制数列上这个数字都为1表示在行、列、九宫格内这个数字都没有被使用我们才能用这个数直接按位与

lowbit运算可以帮助我们在O(1)的时间复杂度内返回当前数里的最后一个1因此用lowbit循环就可以抠出来所有的1

#include

{ios::sync_with_stdio(false);cin.tie(0),

cout.tie(0);//

将所有2^k转化成k(也就是返回二进制数里唯一一个1的位置)for

(int

位置空就累加空位的数量dfs(cnt);puts(str);}

}木棒

乔治拿来一组等长的木棒将它们随机地砍断使得每一节木棍的长度都不超过

然后他又想把这些木棍恢复到为裁截前的状态但忘记了初始时有多少木棒以及木棒的初始长度。

输入格式

先从小到大枚举木棒的长度length看木棍能不能组成该长度的木棒

所有木棍的总长度sum必须能整除木棒的长度length才可能有解不能整除的情况直接回溯不要搜了优化搜索顺序先枚举比较长的木棍使之后的分支较少排除等效冗余

(1)

如果一根木棒里有第一根第二根两根木棍那么先用第一根和先用第二根达成的效果都是一样的因此按照组合数方式枚举

(2)

如果是木棒的第一根木棍失败说明这根木棍没地方放则当前状态一定失败直接回溯不要往下搜了

(4)

如果是木棒的最后一根木棍失败这里的意思是往下dfs找不到解则当前状态一定失败因为放入比这根木棍小的木棍拼接起来的也一定找不到解直接回溯不要往下搜了

#include

{ios::sync_with_stdio(false);cin.tie(0),

cout.tie(0);while

由于要在蛋糕上抹奶油为尽可能节约经费我们希望蛋糕外表面最下一层的下底面除外的面积

QSπ

多层蛋糕给出总体积总层数可以自定义每一层半径和高度使得从上往下看的总面积和总侧面积之和最小求最小值

Rm-1

半径是平方级别高是一次方半径对体积影响更大因此先枚举半径可行性剪枝

(1)

uhu​min{hu1​−1,R2n−V​}最小体积是半径和高都取1时因此可以预处理一下前

minv(u)

mins(u)需要满足以下两个条件才有往下搜的必要否则直接回溯

Vminv(u)n

u}\sum_{k1}^{u}2R_kh_k\frac{2}{R_{u1}}\sum_{k1}^{u}R_uhR_{u1}\frac{2}{R_{u1}}\sum_{k1}^{u}R_u^2h

S1→u​∑k1u​2Rk​hk​Ru1​2​∑k1u​Ru​hRu1​Ru1​2​∑k1u​Ru2​h

S_{1\rightarrow

{ios::sync_with_stdio(false);cin.tie(0),

cout.tie(0);cin