搜索的优化1——剪枝
何谓剪枝？我们可知，搜索是基于搜索树的一个算法，所谓剪枝，就如其字面的意思，剪去一些没有用的枝条。
显然这样可以加快搜索的进程，从而减小时间复杂度。
剪纸的原则：1，正确——不能剪掉含有我们需要的解的枝条，2，准确，3，高效
一些常用的剪纸方法：
1，可行性剪枝（上下界剪枝）
搜索是一种暴力的算法，其思想是有n层，再每层进行枚举等操作，在到达边界条件的时候，判断找到的解是否合法。
通过这个思想我们可以枚举的范围，确定下界和上界，从而达到剪枝的目的。其中确定上界是因为，如果超过枚举上界
往往就不能抵达递归边界了，所以成为可行性剪枝。
例题[NOIP提高组]数的划分
Description
将整数N分成k份，且每份不能为空，任意两个方案不相同（不考虑顺序），问有多少种方案数。
例如 将整数7分成3份，我们认为1 1 5; 1 5 1; 5 1 1是同一种分法。
Input
第一行两个整数N和M
Output
一行代表总的方案数
首先只考虑单纯搜索的做法，只是有K层，每层枚举一个数满足a1+a2+...+ak=n即可，方案数不得冲突。
因为每一层存在枚举一个数字，所以考虑上下界剪枝，我们可以发现因为要求方案不相同，所以ai<=ai+1
所以我们确定了枚举的下界ai-1,再考虑枚举的上界，因为要求分成k份，要求k份的总和为n,所以假设我们
现在枚举到了第pos个数，前pos-1个数的和为sum,为了既满足ai-1<=ai并且k份的总和能够达到n，所以剩下
每一位的大小不能超过(n-sum)/(k-pos),所以只要满足sum+i*(k-pos)<=n即可。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 10 6 7 using namespace std; 8 9 int n,k; 10 int ans; 11 12 inline void dfs(int pre,int sum,int pos) 13 { 14 if(pos==k) 15 { 16 if(sum==n) ans++; 17 return; 18 } 19 for(register int i=pre;sum+i*(k-pos)<=n;++i) 20 dfs(i,sum+i,pos+1); 21 } 22 23 int main() 24 { 25 scanf("%d%d",&n,&k); 26 dfs(1,0,0); 27 printf("%d\n",ans); 28 return 0; 29 }