转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1311605012
大致题意：
给定一堆不定长度的小棒子，问他们能否构成一个正方形。
解题思路：
POJ1011的热身题，DFS+剪枝
本题大致做法就是对所有小棒子长度求和sum，sum就是正方形的周长，sum/4就是边长side。
问题就转变为：这堆小棒子能否刚好组合成为4根长度均为side的大棒子
不难了解，小棒子的长度越长，其灵活性越差。例如长度为5的一根棒子的组合方式要比5根长度为1的棒子的组合方式少，这就是灵活性的体现。
由此，我们首先要对这堆小棒子降序排序，从最长的棒子开始进行DFS
剪枝，有3处可剪：
1、 要组合为正方形，必须满足sum%4==0；
2、 所有小棒子中最长的一根，必须满足Max_length <= side，这是因为小棒子不能折断；
3、 当满足条件1、2时，只需要能组合3条边，就能确定这堆棒子可以组合为正方形。
1 //Memory Time
2 //244K 79MS
3
4 #include<iostream>
5 #include<algorithm>
6 using namespace std;
7
8 int cmp(const void* a,const void* b) //降序
9 {
10 return *(int*)b-*(int*)a;
11 }
12
13 int n; //木棒数量
14 int side; //正方形边长
15 bool dfs(int* stick,bool* vist,int num,int len,int s) //num:已组合的正方形的边数 len:当前组合的边已组合的长度,len<=side
16 { //s:stick[]的搜索起点
17 if(num==3) //剪枝3，当满足剪枝1和2的要求时，只需组合3条side，剩下的棒子必然能够组成最后一条side
18 return true;
19
20 for(int i=s;i<n;i++)
21 {
22 if(vist[i])
23 continue;
24
25 vist[i]=true;
26 if(len+stick[i]<side)
27 {
28 if(dfs(stick,vist,num,len+stick[i],i)) //继续构建当前side
29 return true;
30 }
31 else if(len+stick[i]==side)
32 {
33 if(dfs(stick,vist,num+1,0,0)) //构建新side
34 return true;
35 }
36 vist[i]=false;
37 }
38
39 return false;
40 }
41
42 int main(void)
43 {
44 int time;
45 cin>>time;
46 for(int t=0;t<time;t++)
47 {
48 int sum=0; //所有木棒长度之和
49
50 cin>>n;
51 int* stick=new int[n];
52 bool* vist=new bool[n];
53
54 for(int i=0;i<n;i++)
55 {
56 cin>>stick[i];
57 vist[i]=false;
58
59 sum+=stick[i];
60 }
61
62 if(n<4 || sum%4!=0) //剪枝1，不能构成正方形
63 {
64 cout<<"no"<<endl;
65 continue;
66 }
67
68 qsort(stick,n,sizeof(int),cmp); //降序排列，先组合长棒，因为长棒相对于短棒的组合灵活性较低
69
70 side=sum/4; //边长
71 if(side<stick[0]) //剪枝2，side<max_stick
72 {
73 cout<<"no"<<endl;
74 continue;
75 }
76
77 if(dfs(stick,vist,0,0,0))
78 cout<<"yes"<<endl;
79 else
80 cout<<"no"<<endl;
81
82 delete stick;
83 delete vist;
84 }
85 return 0;
86 }