## **what's 剪枝？** 常用的搜索有Dfs和Bfs。 Bfs的剪枝通常就是判重，因为一般Bfs寻找的是步数最少，重复的话必定不会在之前的情况前产生最优解。 深搜，它的进程近似一颗树(通常叫Dfs树)。 而剪枝就是一种生动的比喻：把不会产生答案的，或不必要的枝条“剪掉”。 剪枝的关键就在于剪枝的判断：什么枝该剪，什么枝不该剪，在什么地方减。 如果当前条件不合法就不再继续搜索，直接return。这是非常好理解的剪枝，搜索初学者都能轻松地掌握，而且也很好想。一般的搜索都会加上。 ``` 一般格式： dfs(int x) { if(x>n)return; if(!check1(x))return; .... return; } ```  如果当前条件所创造出的答案必定比之前的答案大，那么剩下的搜索就毫无必要，甚至可以剪掉。 　　　我们利用某个函数估计出此时条件下答案的‘下界’，将它与已经推出的答案相比，如果不比当前答案小，就可以剪掉。 ```    一般格式： long long ans=987474477434487ll; ... Dfs(int x,...) { if(x... && ...){ans=....;return ...;} if(check2(x)>=ans)return ...; //最优性剪枝 for(int i=1;...;++i) { vis[...]=1; dfs(...); vis[...]=0; } } ``` 一般实现：在搜索取和最大值时，如果后面的全部取最大仍然不比当前答案大就可以返回。 在搜和最小时同理，可以预处理后缀最大/最小和进行快速查询。