poj 2362 Square (dfs+剪枝)

2362 -- Square

　　跟1011的Sticks差不多，不过这里是问给出的长度能否拼成一个正方形。这题数据比较小，不过对剪枝的要求还是差不多的。

主要的剪枝是：

1.由大到小排序后，在拼当前边的第一条棍子的时候必须选用当前没有用过的棍子中最长那条

2.在搞同一条边的时候，下一条棍子不会比之前选了的大

3.同一长度的棍子只搜一次

然后就是代码：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 #define REP(i, n) for (int i = 0; i < (n); i++)
 9 #define REP_1(i, n) for (int i = 1; i <= (n); i++)
10 const int N = 25;
11 int rec[N];
12 bool vis[N];
13 
14 bool dfs(int grp, int s, int n, int sum, int last) {
15     bool ret = false;
16     if (grp == 4) return true;
17     if (s) {
18         for (int i = last + 1; i < n; i++) {
19             if (vis[i]) continue;
20             if (sum - s < rec[i]) continue;
21             if (sum - s == rec[i]) {
22                 vis[i] = true;
23                 ret = dfs(grp + 1, 0, n, sum, i);
24                 vis[i] = false;
25             } else {
26                 vis[i] = true;
27                 ret = dfs(grp, s + rec[i], n, sum, i);
28                 vis[i] = false;
29             }
30             if (ret) return true;
31             while (rec[i + 1] == rec[i]) i++;
32         }
33     } else {
34         REP(i, n) {
35             if (vis[i]) continue;
36             if (rec[i] == sum) {
37                 vis[i] = true;
38                 ret = dfs(grp + 1, 0, n, sum, i);
39                 vis[i] = false;
40             } else {
41                 vis[i] = true;
42                 ret = dfs(grp, rec[i], n, sum, i);
43                 vis[i] = false;
44             }
45             if (ret) return true;
46             else return false;
47         }
48     }
49     return ret;
50 }
51 
52 bool cmp(int a, int b) {
53     return a > b;
54 }
55 
56 int main() {
57 //    freopen("in", "r", stdin);
58     int n, T;
59     cin >> T;
60     while (T-- && cin >> n) {
61         int sum = 0;
62         REP(i, n) {
63             cin >> rec[i];
64             sum += rec[i];
65         }
66         if (sum & 3) {
67             puts("no");
68         } else {
69             sum >>= 2;
70             sort(rec, rec + n, cmp);
71             memset(vis, 0, sizeof(vis));
72             if (rec[0] <= sum && dfs(0, 0, n, sum, -1)) puts("yes");
73             else puts("no");
74         }
75     }
76     return 0;
77 }

View Code

——written by Lyon