题目链接：http://acm.ocrosoft.com/problem.php?cid=1693&pid=2

题目描述

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入

输入文件共有二行。

第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60。

第二行为N个用空个隔开的正整数，表示N根小木棍的长度。

输出

输出文件仅一行，表示要求的原始木棍的最小可能长度。

样例输入

9

 

5 2 1 5 2 1 5 2 1

样例输出

6

思路

这道题是一道深搜剪枝题，主要难点在于剪枝，首先我们来分析一下题目，题目给出我们要求原始木棍的最小可能长度，比如两根长度分别为1,3的木棒，他的原最小长度只可能是4而三根长度为2的木棒他们的原最小长度为2，这么一来我们就可以将小木棒先按从大到小排序从最大的小木棍开始尝试（因为原最小长度的最小值是小木棍中的最大值）一直遍历到所有木棍之和（即最大值）。

而当我们遍历时，可以发现如果要拼凑一个6长度的木棍，用6长度的木棍直接拼凑要比用三个2长度的木棍拼凑要来的有效益的多，因为2长度的木棍更加灵活，所以我们只需要接下去遍历即可

代码

#include<bits/stdc++.h>
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<<i;
    		break;
		}
	}
    return 0;
}