HDU 1455 Sticks

过于经典的深搜题目，而且难度还不算低…..
思路上需要知道多少的长度可以构成合法的长度需要从[最大的长度,所有的长度之和]之间并且这个长度能够使所有长度之和的一个约数
所以我们这么枚举即可从小到大。然后到了关键的地方怎么dfs呢，这里要放一个三元组一个表示当前的位置，一个表示当前拼成的合法的个数一个表示当前的一个合法长度的长
这里需要排序降序排序这样枚举好枚举也是一个降低复杂度的方法…
需要判断一下如果合法的长度满足我们的要求的话就返回即可。这里用的条件判断的dfs，实际上也可以自己设置变量这里就是减少了代码量.
如果我们当前的长度满足了单个的要求那么从第一个开始继续搜索同时合法长度加一
搜索的时候也要记录bk免得一个木棒用了好几次
剪枝一个是如果当前第一个就不满足情况直接返回即可一个就是如果后面跟第一个失败的一样的长度直接过
总的来说剪枝第一是排序这样找的时候好找，第二是如果当前就不满足条件直接跳出，第三如果相同就直接遍历

#include <bits/stdc++.h>
using namespace std;
int bk[10005],a[100005],now,l,n,sum;
bool cmp(int a,int b)
{
	return a>b;
}
int dfs(int p,int cnt,int len)//p当前的位置,cnt当前拼出来了几根木条了,len表示当前拼接的木条的长度
{
	if(cnt==now)
	return 1;
	if(len==l)
	return dfs(1,cnt+1,0);
	for(int i=p;i<=n;i++)
	if(!bk[i]&&len+a[i]<=l)
	{
		bk[i]=1;
		if(dfs(i+1,cnt,len+a[i]))
		return 1;
		bk[i]=0;
		if(len==0)
		return 0;
		while(i<n&&a[i+1]==a[i])
		i++;
	}
	return 0;
}
int main()
{
	while(~scanf("%d",&n)&&n)
	{
		sum=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum+=a[i];
		}
		sort(a+1,a+1+n,cmp);
		for(int i=a[1];i<=sum;i++)
		if(sum%i==0)
		{
			now=sum/i;
			l=i;
			memset(bk,0,sizeof(bk));
			if(dfs(1,0,0))
			{
				printf("%d\n",i);
				break;
			}
		}
	}
}