Sticks

Problem's Link: http://poj.org/problem?id=1011

Mean:

analyse:

爆搜，但是其中蕴含着很多剪枝。

Time complexity: O(n^2)

Source code:

//  Memory   Time//  1347K     0MS//   by : Snarl_jsb//   2014-11-07-17.14#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #define N 1000010#define LL long longusing namespace std;int n,sum,len;vector
                 
                   sti(65);vector
                  
                    used(sti.size());// k-----从第k根开始往后判断// total-----该回合还剩下的长度// sum----未选取的棍子的总长度bool dfs(int k,int total,int sum){ if(total==0) { sum-=len; if(sum==0) { return true; } else { total=len; for(k=0;used[k];++k); //找出未选的最靠前的一根 used[k]=1; //由于从第k根开始选，第k根必选，从k+1根开始搜索 if(dfs(k+1,total-sti[k],sum)) return true; used[k]=0; sum+=len; } } else { for(int i=k;i
                   
                    0) continue; if(total>=sti[i]&&(!used[i])) { total-=sti[i]; used[i]=1; if(dfs(i,total,sum)) return true; total+=sti[i]; used[i]=0; if(sti[i]==total)　　//剪枝：该段的长度正好等于需要的长度，但是该方案行不通，直接返回false退出该函数 　　 break; } } } return false;}bool cmp(int a,int b){ return a>b;}int main(){ ios_base::sync_with_stdio(false); cin.tie(0);// freopen("C:\\Users\\ASUS\\Desktop\\cin.cpp","r",stdin);// freopen("C:\\Users\\ASUS\\Desktop\\cout.cpp","w",stdout); while(cin>>n,n) { sum=0; int tmp; sti.clear(); for(int i=0;i
                    
                     >tmp; sum+=tmp; sti.push_back(tmp); } sort(sti.begin(),sti.end(),cmp); bool flag=false; for(len=sti.front();len<=sum/2;++len) { if(sum%len==0) { if(dfs(0,len,sum)) { cout<
                     
                      <