検索例題解説--棒ちゃん

タイトル
【問題の説明】ジョージは同じ長さの小さな棒を持っていて、彼はこれらの棒を勝手にいくつかの段に切って、各段の長さが50を超えないまで.今、彼は小さな棒を元の姿につなぎ合わせようとしたが、自分が最初に何本の棒とそれらの長さを持っていたか忘れてしまった.各セグメントの棒の長さを与えて、プログラミングは彼に原始の棒の最小可能な長さを見つけるのを助けます.【入力】入力ファイルは2行あります.第1の動作の1つの個別の整数Nは、切り抜いた後の小棒の総数を表し、そのうちN≦60であり、第2の動作Nは、N本の小棒の長さを表すスペースで区切られた正の整数である.【出力】出力ファイルは1行のみで、元の棒の最小可能な長さを表します.[サンプル]stick.in 9 5 2 1 5 2 1 5 2 1 stick.out 6
問題解

#include
#include
#include
int cnt,n,a[61],sum,maxx;
int max(int x,int y){
    return x>y?x:y;
}//      
void init(){
    int x;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(x<=50){//       50 ，     
            a[++cnt]=x;
            sum+=x;//   
            maxx=max(x,maxx);//         
        }
    }
}
int flag;
int b[61];
int t,m;
void search(int l,int s){//l              l 
//s              
    if(flag)return;//     
    if(l==t){//     
        flag=1;//   
        return;//   
    }
    if(s==m){//       
        l++;//l   
        s=0;//    s 
    }
    for(int i=1;i<=cnt;i++){//           
        if(a[i]+s>m || b[i])continue;//    
        if(a[i-1]==a[i] && !b[i])continue;//     (       2 ) 
        b[i]=1;//   
        search(l,s+a[i]);//    
        b[i]=0;//   
        if(flag)return;//     ，   
        if(s==0)return;//      ，          ，   
        //         
    }
}
int comp(const int &a,const int &b){
    return a>b;
}//       
int main(){
    freopen("stick.in","r",stdin);
    freopen("stick.out","w",stdout);//   
    int i,j,k; 
    scanf("%d",&n);
    init();
    std::sort(a+1,a+n+1,comp);//      ，     
    for(i=maxx;i<=sum;i++){//            (  ) 
        if(sum%i==0){//     
            t=sum/i;//t      t  
            m=i;//m            
            flag=0;//    (    ) 
            search(0,0);//   
            if(flag){//              
                printf("%d
",i);//   
                return 0;//     
            }
        }
    }
    return 0;//     
}

以下はオリジナルサイト
http://blog.csdn.net/logo_FC/article/details/52741432