【解题报告】 Stick

【解题报告】 Stick

题目：木棍

解题思路：

深度优先搜索

我们可以用深度优先搜索简单地做出来，没错，是很简单

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int a[100],v[100],n,len,cnt;
bool cmp(int a,int b)
{
	return a>b;
}
bool dfs(int stick,int cab,int last)
{
	if(stick>cnt)
	return true;
	if(cab==len)
	return dfs(stick+1,0,1);
	int fail=0;
	for(int i=last;i<=n;i++)
	{
		if(!v[i]&&cab+a[i]<=len&&fail!=a[i])
		{
			v[i]=1;
			if(dfs(stick,cab+a[i],i+1))
			return true;
			fail=a[i];
			v[i]=0; 
			if(cab==0||cab+a[i]==len)
			return false;
		}
	}
	return false;
}
int main()
{
	while(cin>>n&&n)
	{
		int sum=0,val=0,m=0;
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			if(x<=50)
			{
				a[++m]=x;
				sum+=a[m];
				val=max(val,a[m]);
			}
		}
		n=m;
		sort(a+1,a+1+n,cmp);
		for(len=val;len<=sum;len++)
		{
			if(sum%len)
			continue;
			cnt=sum/len;
			memset(v,0,sizeof(v));
			if(dfs(1,0,1))
			break;
		}
		cout<<len<<endl;
	}
	return 0;
}