题目链接
大致题意：
给定一堆不定长度的小棒子，问他们能否构成一个正方形。
解题思路：
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条边，就能确定这堆棒子可以组合为正方形。
代码语言：javascript复制#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
bool vis[21];
int stick[21];
int n;
int side;
bool cmp(int a, int b)
{
return a > b;
}
bool dfs(int num, int len, int s)//s为搜索起点
{
if (num == 4)
return true;
for (int i = s; i < n; i )
{
if (vis[i])
continue;
vis[i] = true;
if (len stick[i] < side)
{
if (dfs(num, len stick[i], i))
//这里解释游戏为什么有搜索起点这一变量，只有这用到了，如果len stick[i] > side了
//因为是非升序，len stick[i-1] > side必然成立，从0开始就是浪费时间
return true;
/*开始这里我直接 return dfs(num, len stick[i], i)；貌似这样也可以，
但的的确确是错的,直接返回会导致我们少判很多种情况*/
}
else if (len stick[i] == side)
{
if (dfs(num 1, 0, 0))
return true;
//这里同上
}
vis[i] = false;
}
return false;
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
int sum = 0;
for (int i = 0; i < n; i )
{
scanf("%d", &stick[i]);
sum = stick[i];
}
side = sum/4;
sort(stick, stick n, cmp);
if (sum % 4 || side < stick[0])
//这里也可以去掉一些情况
{
puts("no");
continue;
}
memset(vis, false, sizeof(vis));
if (dfs(1, 0, 0))
puts("yes");
else
puts("no");
}
return 0;
}
