The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

一个dfs题，讲解我就copy点大神的了

经典搜索题，黑书上的剪枝例题。剪枝的空间很大，剪枝前写下朴素的搜索框架（黑字部分），枚举原始木棍的长度及由那些小木棍组合。原始木棍长度一定是小木棍总长度的约数，因此可以减少枚举量。

越长的木棍对后面木棍的约束力越大，因此要把小木棍排序，按木棍长度从大到小搜索，这样就能在尽可能靠近根的地方剪枝。（剪枝一）

如果当前木棍能恰好填满一根原始木棍，但因剩余的木棍无法组合出合法解而返回，那么让我们考虑接下来的两种策略，一是用更长的木棍来代替当前木棍，显然这样总长度会超过原始木棍的长度，违法。二是用更短的木棍组合来代替这根木棍，他们的总长恰好是当前木棍的长度，但是由于这些替代木棍在后面的搜索中无法得到合法解，当前木棍也不可能替代这些木棍组合出合法解。因为当前木棍的做的事这些替代木棍也能做到。所以，当出现加上某根木棍恰好能填满一根原始木棍，但由在后面的搜索中失败了，就不必考虑其他木棍了，直接退出当前的枚举。（剪枝二）

显然最后一根木棍是不必搜索的，因为原始木棍长度是总木棍长度的约数。（算不上剪枝）

考虑每根原始木棍的第一根木棍，如果当前枚举的木棍长度无法得出合法解，就不必考虑下一根木棍了，当前木棍一定是作为某根原始木棍的第一根木棍的，现在不行，以后也不可能得出合法解。也就是说每根原始木棍的第一根小木棍一定要成功，否则就返回。（剪枝四）

剩下一个通用的剪枝就是跳过重复长度的木棍，当前木棍跟它后面木棍的无法得出合法解，后面跟它一样长度的木棍也不可能得到合法解，因为后面相同长度木棍能做到的，前面这根木棍也能做到。（剪枝五）

这题主要就是剪枝，看了别人的代码看了好久才写的

#include<iostream>
#include<algorithm>
using namespace std;

int a[70],visit[70],len,n;

bool cmp(const int a,const int b)
{
	return a>b;
}

bool dfs(int f,int i,int sum)
{
	int j;
	if(i==0)
	{
		if(sum==len)
			return true;//全部的都已经找完了，都匹配
		i=len;
		for(j=0;visit[j];j++)
			;
		visit[j]=1;
		if(dfs(j+1,i-a[j],sum-len))//此处j+1是因为j已经搜过了
		{
			return true;
		}
		visit[j]=0;//失败了
	}
	else
	{
		for(j=f;j<n;j++)
		{
			if(visit[j])
				continue;
			if(j>0&&a[j]==a[j-1]&&!visit[j-1])
			{
				continue;
			}
			visit[j]=1;
			if(a[j]<=i&&dfs(j+1,i-a[j],sum))//这里j+1和上面意思一样，原来看别人的写的是j，让我纠结了好久，加不加1只是对结果没影响
				return true;
			visit[j]=0;
			if(a[j]==i)//刚好把木棒填满，并且搜索失败，这种情况不可能了，无论如何满足不了题意的
				break;
		}
	}
	return false;
}
int main()
{
	int i,j,sum;
	while(scanf("%d",&n)!=EOF&&n)
	{
		for(i=0;i<n;i++)
			visit[i]=0;
		sum=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",a+i);
			sum+=a[i];
		}
		sort(a,a+n,cmp);
		j=sum/2;
		for(i=a[0];i<=j;i++)
		{
			len=i;
			if(sum%i==0)
			{
				if(dfs(0,i,sum))//序号，还差的长度(不包括当前棒)，总木棒剩余的长度
				break;//这个dfs有点特殊，dfs里面的意思不太一样，它没有标记0，这是为了方便写
			}
		}
		if(i>j)
			printf("%d\n",sum);
		else printf("%d\n",i);
	}
	return 0;
}
/*
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
*/

优质内容筛选与推荐>>
1、通过银行卡号识别归属银行，php方式
2、[ 题解 ] [ 排序 ] F. Out of Sorts II
3、URL Loading System官方文档翻译<一>
4、11 linux nginx上安装ecshop 案例
5、c编译步骤