> /*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());			
> 	}
> }

• 总算过了，把深搜当贪心在用了 (0) anotherh 2006-03-12 10:00:49
  • Re:总算过了，把深搜当贪心在用了 (0) yueliang 2007-04-08 19:49:24