poj 2362（剪枝）

题意：给定一堆不定长度的小棒子，问他们能否构成一个正方形。

解题思路：最开始写的时候把题意弄错了，以为只要能够从中取出一部分构成矩形即可。。。。

这里注意一下几个剪枝的地方：

1）要把所有的棒子都用上且组成正方形，那么sum % 4 = 0；

2）如果棒子长度小于4，肯定是不行的

3）如果棒子中有长度大于sum/4的，肯定是组成不了正方形的。

注意：对棒子长度进行排序时，从大到小的顺序用时更少。

AC:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int len[25],n,sum;
bool used[25],flag;

bool cmp(int a,int b)
{
	return a > b;
}

bool dfs(int cur,int tmp,int index)	//cur表示当前所取的木棍编号，tmp表示当前边的长度，index表示4条边中的编号
{
	if(index > 4) return true;
	if(tmp + len[n] > sum) return false;
	for(int i = cur+1; i <= n; i++)
	{
		if(used[i] == true) continue;
		if(tmp + len[i] > sum) continue;
		used[i] = true;
		if(tmp + len[i] == sum)	
		{
			if(dfs(0,0,index+1))
				return true;
		}
		else   // tmp + len[i] < sum
		{
			if(dfs(i,tmp+len[i],index))
				return true;
		}
		used[i] = false;
	}
	return false;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		for(int i = 1; i <= n; i++)
			scanf("%d",&len[i]);
		sort(len+1,len+1+n,cmp);
		sum = 0;
		for(int i = 1; i <= n; i++)
			sum += len[i];
		memset(used,false,sizeof(used));
		if(sum % 4 != 0 || n < 4 || sum / 4 < len[1])
			printf("no\n");
		else
		{
			sum /= 4; 
			if(dfs(0,0,1))
				printf("yes\n");
			else printf("no\n");
		}
	}
	return 0;
}