poj1011(DFS)

164K

16MS

C++

2578B

解题思路：一个棍一个棍的组合，组合好第i根，再组合第i+1根，注意要剪好枝。
若前面的一个组合未能成功，当该组合再次出现时也不能成功。
#include<stdio.h>
int flag=0;//标志棍组合的当前顺序
int flagall=0;//标志是否成立
int a[65],b[65],max=0;//a保存当前输入数，b标志是否使用
int main()
{
	int n,i;
	void search(int m,int k,int n);
	int findmax(int n);
	int sum(int n);
	void sort(int n);
	scanf("%d",&n);
	while(n)
	{
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		sort(n);
		search(findmax(n),sum(n),n);
 		scanf("%d",&n);
		for(i=0;i<65;i++)
			a[i]=0;
	}
	return 1;
}
void sort(int n)//排序
{
	int temp;
	for(int i=0;i<n;i++)
		for(int j=0;j<n-i;j++)
			if(a[j]<a[j+1])
			{
				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
}
int findmax(int n)
{
	int max=0;
	for(int i=0;i<n;i++)
		if(a[i]>max)
			max=a[i];
		return max;
}
int sum(int n)
{
	int s=0;
	for(int i=0;i<n;i++)
		s=s+a[i];
	return s;
}
int findNotUsed(int start,int n)//找到未使用的结点的下标
{
	int i;
	for(i=start;i<n;i++)
		if(!b[i])
			break;
	if(!b[i])
		return i;
	else
		return n-1;
}
int find(int count)
{
	for(int i=0;i<65;i++)
		if(b[i]==count)
			return i;
}
int findnostart()
{
	for(int i=0;i<65;i++)
		if(!b[i])
			return i;
}
void isRight(int start,int m,int k,int count,int number,int n)//判断棍长为m时是否成立
{
	int index,form;
	if(start>=n)
		return ;
	if(flag==number&&count==number+1)  //组合成立
	{
		flagall=1;
		return ;
	}
	index=findNotUsed(start,n);
    if(!b[index]&&index<n)
	{
		if(a[index]+k==m)
		{
			b[index]=count;
			flag=count;
			if(find(count)==max)//找到的组合是以最长的棍开始的，则进入下一个棍的搜索
			{
				form=max;
				max=findnostart();//剩余的棍中最长的那个的下标
				isRight(0,m,0,count+1,number,n);//进入下一个棍的组合
				max=form;
			}
			b[index]=0;/////////////////////////////////////////////////恢复
			flag=count-1;
		}
		else if(a[index]+k>m)
		{
			b[index]=0;
			while(index+1<n&&a[index+1]==a[index])//剪枝
					index++;
			isRight(index+1,m,k,count,number,n);
		}
		else
		{	
			if(index!=0&&a[index-1]==a[index]&&!b[index-1])//剪枝，前一个点不用，则后一个值相同的结点肯定不用
			{
				while(index+1<n&&a[index+1]==a[index])
					index++;
				isRight(index+1,m,k,count,number,n);
			}
			else
			{
	    		b[index]=count;
				isRight(index+1,m,k+a[index],count,number,n);
				if(!flagall)//剪枝
				{
					b[index]=0;
					isRight(index+1,m,k,count,number,n);
				}
			}
		}
	}
}
void search(int m,int k,int n)
{
     if(m==k)
	{
		printf("%d\n",m);
		return ;
	}
    if(k%m==0)
	{
		for(int i=0;i<65;i++)
			b[i]=0;
		max=0;
		isRight(0,m,0,1,k/m,n);
		if(flagall)
		{
			flagall=0;
	    	printf("%d\n",m);
		}
		else
	    	search(m+1,k,n);
	}
	else
		search(m+1,k,n);
}