1011.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include <stdlib.h>
long total,stick[200],n,flag;
long used[200];
long max[200];
long len;
int compare(const void *arg1,const void *arg2)
{
	long a=*(long *)arg1;
	long b=*(long *)arg2;

	return b-a;
}


int search(long p,long now,long next)
{
	long i;
	if (flag) return 0;

	if (p==total && now==len){
		flag=1;
		return 0;
	}
         /*下面的部分有改动*/
	if (now==len){
		for (i=0;i<n;i++)
                     if (!used[i]) break;
                  used[i]=1;
                  search(p+1,stick[i],i+1);
                  used[i]=0;
		return 0;
	}

	if (now==0) next=0;
	if (next>=n) return 0;
	if (next>0 && used[next-1]==0 && stick[next]==stick[next-1]) return 0;
	for(i=next;i<n;i++){
		if (i>max[p-1] && used[i]==0 && (now+stick[i])<=len) {
			used[i]=1;

			if (now==0) max[p]=i;

			search(p,now+stick[i],i+1);
			used[i]=0;
			if (flag) return 0;
			if (stick[i]==(len-now)){
			   if (p==total) flag=1;
			   return 0;
			}
		}

	}
	return 0;
}



int main()
{
	long i;
	long sum;
	long m;
	while(cin>>n && n!=0){
		m=0;
		sum=0;
		flag=0;
		memset(used,0,sizeof(used));
		memset(stick,0,sizeof(stick));
		for(i=0;i<n;i++){
			cin>>stick[i];
			if (stick[i]==0) used[i]=0;
			sum+=stick[i];
			if (stick[i]>m) m=stick[i];
		}
		qsort(stick,n,sizeof(long),compare);
		for(len=m;len<=sum;len++)
		   if (sum%len==0){
		      total=sum/len;
		      max[0]=-1;
		      search(0,len,0); //有改动
		      if (flag) break;
		   }


		cout<<len<<endl;
	}
	return 0;
}