#include<iostream>
#include<cstdlib>
using namespace std;
int s[100];
bool bo[100];
int all,ave;
bool b,bb;
int cmp(const void*a,const void*b)
{
	return -(*(int *)a-*(int *)b);
}
void search(int now,int n,int nowl,int num,int j)
{
	//cout<<nowl<<endl;
	if(now==n-1)bb=true;
	if(bb)return;
	if(nowl==ave)
	{
		int ii;
		for(ii=0;ii<num;ii++){
			if(bo[ii]==false)break;
		}
		bo[ii]=true;
		search(now+1,n,s[ii],num,ii+1);
	}
	else{
		int temp=-1;
		for(int i=j;i<num;i++)
		{
			if(bo[i]==false)
			{
				if(nowl+s[i]>ave){continue;}
				else if(i>=1&&s[i]==temp)continue;
				else if(nowl+s[i]==ave)
				{
					bo[i]=true;
					search(now,n,ave,num,i+1);
					return;
				}
				else 
				{
					bo[i]=true;
					search(now,n,nowl+s[i],num,i+1);
					if(bb)return;
					if(!b)return;
					bo[i]=false;
				}
				temp=s[i];
			}
			if(bb)return;
			if(!b)return;
		}
	}
}
int main()
{
	int n;
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	while(cin>>n)
	{
		if(n==0)break;
		all=0;
		for(int i=0;i<n;i++)
		{
			cin>>s[i];
			bo[i]=false;
			all+=s[i];
		}
		qsort(s,n,sizeof(int),cmp);
		bb=false;
		int i;
		for(i=s[0];i<all;i++)
		{
			if(all%i==0)
			{
				for(int j=0;j<n;j++)
				bo[j]=false;
				ave=i;
				b=true;
				bo[0]=true;
				search(0,all/i,s[0],n,1);
				if(bb)break;
				//cout<<endl;
			}
		}
		int answer;
		if(bb)answer=i;
		else answer=all;
		cout<<i<<endl;
	}
	return 0;
}
大牛们帮忙看看

• Re:谁帮帮我，wa得不行了，论坛给得测试数据都过，连变态数据都顺秒，woj上也能ac，在这就wa (1706) 346248129 2008-05-22 16:22:06
  • Re:谁帮帮我，wa得不行了，论坛给得测试数据都过，连变态数据都顺秒，woj上也能ac，在这就wa (35) 346248129 2008-05-22 16:22:46