poj2362——Square

题意：给出N个数据，求是否能组成正方形。

思路：dfs+剪枝。

剪枝思路：

1,数的总和能否被4整除;

2,最大边是否超过平均数;

3,如果某个数作为边的第一个数(在数已经降序排列的情况下)，不能满足，则返回上一层。因为它做为第一个数走不下去，那么在后面的其他边也会有同样的情况(即又会出现在第一数的位置)，因为每次循环要么从0开始，要么从star开始。在略过这根之后，想要完整拼完这个正方形，意味着要从0开始，这时候，它又会出现在第一个数的位置;

4,如果某个数作为边的最后一个数，不能满足，同样返回上一层。因为它作为最后一个数走不下去，你用其他小于它的数来代替。那么，如果要拼成一个正方形，且用完所有数，那么它在后面也必然会用上。这样就可以把它和前面代替它的那些数调换。-------->矛盾;

5,如果a[1]==a[2]，a[1]已证明不行，a[2]也不用去试了;

6,对star的标记。感觉这个非常重要。可以跳过很多不必的探查!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int a[25],n,average;
bool vis[25];
bool dfs(int num,int len,int star)
{
	int i;
	if(len==average){num++;len=0;star=0;}
	if(num==3)
		return true;
	for(i=star;i<n;i++)                             ////////////剪枝6
	{
		if(!vis[i]) continue;
		if(a[i]+len>average) continue;             ///////////这个也算吧，如果已超过平均数，你还会再用a[i]吗？
		if(i!=0&&vis[i-1]&&a[i]==a[i-1]) continue;   //////////剪枝5
		vis[i]=false;
		if(dfs(num,len+a[i],i+1))return true;
		vis[i]=true;
		if(a[i]+len==average||len==0)                /////////剪枝3&&剪枝4
			break;
	}
	return false;
}
int cmp(const void *b,const void *c)
{
	return *(int *)c-*(int *)b;
}
int main()
{
	int t,i,sum;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
			scanf("%d",&a[i]);
		sum=0;
		qsort(a,n,sizeof(a[0]),cmp);
		for(i=0;i<n;i++)
			sum+=a[i];
		average=sum/4;
		if(sum%4!=0)                       /////////////////剪枝1
		{
			printf("no\n");
		}
		else if(a[0]>average)              //////////////////剪枝2
		{
			printf("no\n");
		}
		else 
		{
			memset(vis,true,sizeof(vis));
			if(dfs(0,0,0)) printf("yes\n");
			else printf("no\n");
		}
	}
}