搜索专题

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 <iostream>
#include <algorithm>
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=i;j<n;++j)
        {
            if(j>0&&(sticks[j]==sticks[j-1]&&!used[j-1]))  //剪枝2：前后两根长度相等时，如果前面那根没被使用，也就是由前面那根
                continue;                                                //开始搜索不到正确结果，那么再从这根开始也肯定搜索不出正确结果，此剪枝威力较大
                                                                                  
            if(!used[j]&&l>=sticks[j])   //剪枝3：最简单的剪枝，要拼成一根大棍子还需要的长度L>=当前小棍子长度，才能选用                           
            {
                l-=sticks[j];
                used[j]=1;
                if(dfs(j,l,t))return true;
                    
                l+=sticks[j];
                used[j]=0;
                
                if(sticks[j]==l)    //剪枝4：威力巨大的剪枝，程序要运行到此处说明往下的搜索失败，若本次的小棍长度刚好填满剩下长度，但是后
                    break;           //面的搜索失败，则应该返回上一层
            }
        }
    }
    return false;