hdoj1258

http://acm.hdu.edu.cn/showproblem.php?pid=1258
本题爆搜~,关键是如何防止重复。
其实一个if语句即可:

if(!visit[j-1] && a[j]==a[j-1])
{
   ;               
 }
else
{

}

在要选择a[j]时visit[j-1]==0说明两者之间不是同一方案的前后继关系,若此时a[j]==a[j-1],则a[j]不必考虑。(假设a[j-3]+a[j-1]=t,a[j-1]==a[j],那么显然a[j-3]+a[j]=t的方案和前者重复,不必考虑)
如果不加!visit[j-1]会怎样?
如果不加,可能会造成漏选方案。
例如:t=4;a[j]=1,a[j+1]=1;
2+1+1=4
显然,第2个1是无法选上的,因为a[j]==a[j-1].但其实visit[j-1]==1,所以a[j-1]和a[j]不是并列关系,也就是这两个1必须看成不同的,它们是同一种方案的前后继关系。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int sum=0,n,t;
int visit[13];
int a[13];
int queue[14];
int iq=0;
bool flag=false;
void dfs(int i)
{
	visit[i]=1;
	int j,k;
	if(sum==t)
	{
		flag=true;
		printf("%d",queue[0]);
		for(k=1;k<=iq-1;k++)
			printf("+%d",queue[k]);
		printf("\n");
		return;
	
	}
	for(j=i+1;j<=n;j++)
	{
		if(sum+a[j]<=t && !visit[j])
		    if(!visit[j-1] && a[j]==a[j-1])
		    {
               ;               
                           
            }
            else
            {
                
    			queue[iq++]=a[j];
    			sum+=a[j];
    			dfs(j);
    			visit[j]=0;
    			sum-=a[j];
    			iq--;
    		}
	
	}

return;
}
int main()
{
	int i;
	scanf("%d %d",&t,&n);
	while(n!=0)
	{
		iq=0;
		flag=false;
		sum=0;
		memset(queue,0,sizeof(queue));
		memset(visit,0,sizeof(visit));
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		printf("Sums of %d:\n",t);
		dfs(0);
		if(!flag)
			printf("NONE\n");
		scanf("%d %d",&t,&n);
	}
//system("pause");
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>