题意:
给出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;
}