这道题和poj的拯救少林神棍是一样的题目。

要用给出的小棍凑成等长的棍子，求能凑成的棍子的最小长度。

直观的包里思路就是枚举所有可能的长度，然后不停的测试小棍组合，先把小棍加入组合，然后不合适就推翻这一根小棍，再测试下一个小棍，直到推翻所有的小棍。

在枚举的时候，我们只需从最长的小棍长，枚举到小棍总长的一半就行了。然后如果再不符合的话，那么就说明所有小棍只能组合成一根棍子了。

我原先看过关于poj上拯救少林神棍这道题目的详细讲解。一个DFS搜索题，这里DFS共有四种剪枝方案：

1. 所给出的小棍长度可能有重复，如果含有某一小棍的组合方案被推翻了，那么和它同样长的小棍也没必要尝试
2. 为了减少重复的测试方案，比如测试了棍子1 2 3方案不合适，后面又测试了小棍子1 3 2 是没必要的。那么一定要按顺序开始测试，在当前小棍被加入到组合方案时，如还没有组成该目标长度，那么接下来要测试的小棍要从当前小棍的下一个开始测试。
3. 要凑成某一目标长度的棍子，其中组成它的第一根小棍，怎么也无法和其他小棍凑出这个长度，那么没必要推翻这第一根小棍，直接推翻这个目标长度就可以了。
4. 如果加上一个小棍x凑成了目标长度，但剩下的小棍再也凑不出这个长度了。那么没必要推翻这个小棍x，去测试其他的小棍，直接推翻这个目标长度就可以了。

开始我四种剪枝都写上了。但还是超时，无语了。

最后发现在DFS之外的main函数里有个剪枝我没有使用，要测试的长度一定要是总长度的因数，否则就没有必要测试这个长度。因为棍子是一样长的，每一根的长度当然要是总长度的因数才对。就是这个剪枝没有写导致我超时的。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;bool used[64];int len[64],n,l,last;bool dfs(int r,int m){    if(r==0&&m==0)        return true;    if(m==0)        m=l;    int start=0;    if(m!=l)        start=last+1;    for(int i=0;i
        
         0)            {                if(used[i-1]==false&&len[i]==len[i-1])                    continue;            }            used[i]=true;            last=i;            if(dfs(r-1,m-len[i]))                return true;            else            {                used[i]=false;                if(len[i]==m||m==l)                    return false;            }        }    }    return false;}int main(){    while(cin>>n)    {        if(!n)        break;        int total=0;        for(int i=0;i
         
          >len[i]; total+=len[i]; } sort(len,len+n,greater
          
           ()); for(l=len[0];l<=total/2;l++) { if(total%l)//就是没写这个超时的。。 continue; memset(used,false,sizeof(used)); if(dfs(n,l)) { cout<
           
            <
            
             total/2) cout<
             
              <