题意：
给出N条木棍的长度，问能不能用这些木棍拼成一个正方形。
思路：
这题一开始想复杂了，后来发现只要2个最简单的剪枝题目就能79ms通过了。
再加上一个比较屌的剪枝就可以到16ms。
参考了网上的代码，很多份代码如出一辙。思想十分牛逼。
剪枝1：
所有木棍的长度必须能被4整除
剪枝2：
最长的木棍不能长于正方形的边长
这两个是最容易想到的，用上这两个可以79ms通过
剪枝3：
同样长度的木棍的同样数量的组合只搜索一次。
这个剪枝需要将木棍从大到小排列，在搜索的时候加一句代码就行了，代码很巧妙。
由于数据问题，这个剪枝貌似不管用。
剪枝4：
每条边的木棍按照从大到小的顺序拼接
如果某条木棍不能够作为某边的第一条木棍，那比它短的也不行
想一想还是可以理解，后面的边始终会用到这条长的棍子，那时候可供选择的木棍更少
所以在前面的边拼不成，在后面的边更加拼不成
这个剪枝非常牛逼，不知道谁想出来的，代码只需要一句。太牛逼了。
由于数据的N比较小，这个剪枝相当管用。
无法实现的理想化剪枝：
如果在枚举中，发现用一条长的棍子枚举失败，那么几条短的棍子组成同样长度的棍子也必然不用试验。
这个很理想，但是实现的代价很大。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 1+2 : 79ms
// 1+2+3 : 79ms
// 1+2+4 : 16ms
// 1+2+3+4: 16ms
int part, N;
int len[128];
char used[128];
int cmp(const void *a, const void *b)
{
return *(int *)b - *(int *)a;
}
int dfs(int side, int start, int left)
{
int i;
if (!left) {
left = part;
side++;
start = 0;
}
if (side == 4)
return 1;
for (i = start; i < N; i++) {
if (len[i] > left)
continue;
if (used[i])
continue;
// 3
if (i && !used[i - 1] && len[i] == len[i - 1])
continue;
used[i] = 1;
if (dfs(side, i + 1, left - len[i]))
return 1;
used[i] = 0;
// 4
if (left == part)
return 0;
}
return 0;
}
int solve()
{
int i, sum;
scanf("%d", &N);
sum = 0;
for (i = 0; i < N; i++) {
scanf("%d", &len[i]);
sum += len[i];
}
// 1
if (sum % 4)
return 0;
part = sum / 4;
qsort(len, N, sizeof(len[0]), cmp);
// 2
if (len[0] > part)
return 0;
memset(used, 0, N);
return dfs(0, 0, part);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
printf("%s\n", solve() ? "yes" : "no");
return 0;
}