HDU-1518 Square dfs+剪枝

該題問給定的棍子能否組成一個正方形。首先我們要判定是否總長度是4的倍數，然后再決定是否存在某條邊大于組合邊長。

搜索的過程中也是可以進行剪枝了。

首先將邊排序，我們可以假定所有的組合邊由大小遞減的邊組成，那么我們在搜索的時候就不用再往前找邊了。

其次我們可以確定任何一條邊都一定在一條組合邊中，那么當我們以任意一條邊開搜的情況下無解的話，那么我們就可以直接返回no了。

最后在搜索某條邊無解的情況下，我們可以把相同大小的邊略過，因為前面相同長度的邊都無法安排出一種方案，在少一條相同邊情況下肯定也就無法給出安排了。

代碼如下：

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int N, seq[25], use[25], mode;bool dfs(int cap, int last, int num)
{if (num == N) {return true;}if (cap == 0) {if (dfs(mode, N+1, num)) {return true;}else {return false;}}else {for (int i = last-1; i >= 1; --i) {if (cap >= seq[i] && !use[i]) {use[i] = 1;if (dfs(cap-seq[i], i, num + 1)) {return true;}else {use[i] = 0;if (i == N) {return false;}while (seq[i-1] == seq[i]) --i;} }}}return false;
}int main()
{int T, sum, Max;scanf("%d", &T);while (T--) {sum = 0, Max = -1;memset(use, 0, sizeof (use));scanf("%d", &N);for (int i = 1; i <= N; ++i) {scanf("%d", &seq[i]);Max = max(Max, seq[i]);sum += seq[i];}if (sum % 4 != 0 || Max > sum / 4) {puts("no");continue;}sort(seq+1, seq+N+1);mode = sum / 4; // 每一邊的大小printf(dfs(mode, N+1, 0) ? "yes\n" : "no\n");}return 0;
}