題意：
給出N條木棍的長(zhǎng)度，問(wèn)能不能用這些木棍拼成一個(gè)正方形。
思路：
這題一開始想復(fù)雜了，后來(lái)發(fā)現(xiàn)只要2個(gè)最簡(jiǎn)單的剪枝題目就能79ms通過(guò)了。
再加上一個(gè)比較屌的剪枝就可以到16ms。
參考了網(wǎng)上的代碼，很多份代碼如出一轍。思想十分牛逼。
剪枝1：
所有木棍的長(zhǎng)度必須能被4整除
剪枝2：
最長(zhǎng)的木棍不能長(zhǎng)于正方形的邊長(zhǎng)
這兩個(gè)是最容易想到的，用上這兩個(gè)可以79ms通過(guò)
剪枝3：
同樣長(zhǎng)度的木棍的同樣數(shù)量的組合只搜索一次。
這個(gè)剪枝需要將木棍從大到小排列，在搜索的時(shí)候加一句代碼就行了，代碼很巧妙。
由于數(shù)據(jù)問(wèn)題，這個(gè)剪枝貌似不管用。
剪枝4：
每條邊的木棍按照從大到小的順序拼接
如果某條木棍不能夠作為某邊的第一條木棍，那比它短的也不行
想一想還是可以理解，后面的邊始終會(huì)用到這條長(zhǎng)的棍子，那時(shí)候可供選擇的木棍更少
所以在前面的邊拼不成，在后面的邊更加拼不成
這個(gè)剪枝非常牛逼，不知道誰(shuí)想出來(lái)的，代碼只需要一句。太牛逼了。
由于數(shù)據(jù)的N比較小，這個(gè)剪枝相當(dāng)管用。
無(wú)法實(shí)現(xiàn)的理想化剪枝：
如果在枚舉中，發(fā)現(xiàn)用一條長(zhǎng)的棍子枚舉失敗，那么幾條短的棍子組成同樣長(zhǎng)度的棍子也必然不用試驗(yàn)。
這個(gè)很理想，但是實(shí)現(xiàn)的代價(jià)很大。
#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;
}