POJ1011 Sticks 搜索+强剪枝（终于AC 了，分享经验） 这个题目是不是贪心的，我就是第一次用了贪心，一直WA， 相当的悲剧，贪心错误的sample：7 15 11 8 8 8 4 3 2 1，所以大家还是全部搜索
但是全部搜索必须剪枝，不然肯定是TLE的，而且本体属于强剪枝，少剪了也是TLE
经典搜索题，果然是到处充斥着剪枝才能过啊，我的代码离剪到极限还差很多 题目给出一大堆小棍子的长度，需要把他们拼成几根长度相等的大棍子，求大棍子的最短长度 看自己剪枝方法的效果时候，可以添设一个变量来记录递归次数 如剪枝4： 没有这个剪枝的情况下对以下数据需要40 万次递归，而加上这个剪枝后减少到了4 万多次 对数据： 45 15 3 2 4 11 1 8 8 8 15 3 2 4 11 1 8 8 8 15 3 2 4 11 1 8 8 8 15 3 2 4 11 1 8 8 8 15 3 2 4 11 1 8 8 8 #include #include using namespace std; int sticks[65]; int used[65]; int n,len; bool dfs(int i,int l,int t)//i 为当前试取的棍子序号,l 为要拼成一根完整的棍子还需要的长度,t 初值为所有棍子总长度 { if(l==0) { t-=len; if(t==0)return true; for(i=0;used[i];++i); //剪枝1： 搜索下一根大棍子的时候，找到第一个还没有使用的小棍子开始 used[i]=1; //由于排序过，找到的第一根肯定最长，也肯定要使用，所以从下一根开始搜索 if(dfs(i+1,len-sticks[i],t))return true; used[i]=0; t+=len; } else { for(int j=
