/*pku 1011*/
#include<stdio.h>
#include<stdlib.h>
#define N 80
int sticks[N],a[N],n,all;

int cmp(const void *a,const void *b)
{
	return *((int *)b)-*((int *)a);
}

int dfs(int len,int begin,int end)/*END代表原长度，就是找到这么长后一次搜索结束*/
{
	int ii,jj,temp;
	for(ii=begin;ii<n;ii++)
	{	
		if(a[ii])
		{		
			if(len+a[ii]==end)
			{
				a[ii]=0;
				return 1;
			}
			else if(len+a[ii]<end){	
				
				temp=dfs(len+a[ii],ii+1,end);
				if(temp) 
				{
					a[ii]=0;
					return 1;
				}
			}					
		}
	}
	return 0;
}

int find_small()
{		
	int jj,kk,judge,ori;
	for(ori=sticks[0];ori<=all;ori++)
	{						
		if(!(all%ori))
		{
			for(jj=0;jj<n;jj++)
				a[jj]=sticks[jj];	
			for(jj=1,judge=1;jj<=all/ori&&judge;jj++)/*找到JJ次完整的*/
				{
					kk=0;
					while(!a[kk])
						kk++;
					judge=dfs(0,kk,ori);				
				}
			if(judge)
				return ori;
		}
	}
}

int main()
{
	int ii;
	while(scanf("%d",&n)&&n)
	{
	
		for(ii=all=0;ii<n;ii++)
		{
			scanf("%d",sticks+ii);
            all+=sticks[ii];
		}
		qsort(sticks,n,sizeof(sticks[0]),cmp);
		/*printf("%d\n",all);*/				
		printf("%d\n",find_small());			
	}
}

• 我已经测了N组数据了，都没发现什么问题啊 (1316) anotherh 2006-03-11 18:47:32
  • 总算过了，把深搜当贪心在用了 (0) anotherh 2006-03-12 10:00:49
    • Re:总算过了，把深搜当贪心在用了 (0) yueliang 2007-04-08 19:49:24