質問C:【例題3】小さな棒

タイトルリンク:http://acm.ocrosoft.com/problem.php?cid=1693&pid=2
タイトルの説明
ジョージは同じ長さの小さな棒を持っていて、彼はこれらの棒を勝手にいくつかの段に切って、各段の長さが50を超えないまで.
今、彼は小さな棒を元の姿につなぎ合わせようとしたが、自分が最初に何本の棒とそれらの長さを持っていたか忘れてしまった.
各セグメントの棒の長さを与えて、プログラミングは彼に原始の棒の最小可能な長さを見つけるのを助けます.
入力
入力ファイルは2行あります.
第1の挙動の個別の整数Nは、切り捨てられた後の小棒の総数を表し、そのうちN≦60である.
第2の挙動N個は空個で区切られた正の整数であり,N本の小棒の長さを表す.
しゅつりょく
出力ファイルは1行のみで、元の棒の最小可能な長さを示します.
サンプル入力
9
 
5 2 1 5 2 1 5 2 1
サンプル出力
6
構想
この問題は深く枝を切る問題で、主な難点は枝を切ることです.まず、問題を分析してみましょう.これにより、小さな棒を最初に大きな棒から小さい棒に並べて、最大の棒から試してみることができます(元の最小長の最小値は小さな棒の最大値であるため)、すべての棒の和(つまり最大値)まで遍歴することができます.
私达が遍歴する时、もし1つの6长い木の棒を组み合わせるならば、6长い木の棒で直接组み合わせるのは3つの2长い木の棒で组み合わせるよりも利益があることを発见することができて、2长い木の棒は更に柔软で、だから私达はただ遍歴するだけでいいです
コード#コード#

#include
using namespace std;
int n,k;
int a[1000001];
int sum=0;
int f[1000001];//       
bool cmp (int x,int y)//     
{
	return x>y; 
}
/*
len       
now          
num         
x            
*/ 
bool dfs(int x,int len,int now,int num)//         --         --         
{
    if(num==sum/len) //       ==          ，  true 
	return 1;
    if(now==len)//                   ，                     ，  true 
    { 
	    if(dfs(1,len,0,num+1)) 
		return 1;
	} 
    for(int i=x;i<=n;i++)//  x       
    {
	    if(!f[i]&&now+a[i]<=len)
	    {
	        f[i]=1;//   
	        if(dfs(i+1,len,now+a[i],num)) //     dfs 
			return 1;
	        f[i]=0;//      
	        if(a[i]==len-now||now==0) //                
			break;
	        while(a[i]==a[i+1]) //           
			i++;
	    }
	}
    
    return 0;
}
int main(){  
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
    	sum+=a[i];
	}
    sort(a+1,a+1+n,cmp);
    for(int i=a[1];i<=sum;i++)
    {
    	if(sum%i!=0)//      ，     
    	continue;
    	if(dfs(1,i,0,0))
    	{
    		cout<