poj 2362 Square（dfs, 剪枝）

Square Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 23828 Accepted: 8253

Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

Sample Input

3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5

Sample Output

yes no yes

Source

Waterloo local 2002.09.21

思路：重在剪枝

代码：

#include<algorithm> #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 25; int a[maxn], n, avg, flag, have; bool book[maxn]; void dfs(int fin, int num, int cur) { if(flag) return ; if(fin == 4) { flag = 1; return ; } if(num == avg) { dfs(fin+1, 0, 0); return; } for(int i = cur; i < n; i++) { if(num+a[i] > avg) return ;<span style="white-space:pre"> </span>//剪枝2，因为对木棍排过序，搜到该棍过长，那后面的肯定更加长，不用搜了 if(!book[i] && num+a[i] <= avg) { book[i] = 1; dfs(fin, num+a[i], i+1); book[i] = 0; if(flag) return ;<span style="white-space:pre"> </span>//剪枝3，一搜到就返回 } } } int main(void) { int t, maxlen; cin >> t; while(t--) { memset(book, 0, sizeof(book)); avg = flag = maxlen = 0; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", &a[i]), avg += a[i], maxlen = max(maxlen, a[i]); if(avg % 4 || maxlen > avg/4) { printf("no\n"); continue ; }<span style="white-space:pre"> </span>//剪枝1，若最长的木棍大于边长，边长不能被4整除，肯定不行 sort(a, a+n);<span style="white-space:pre"> </span> avg /= 4; dfs(0, 0, 0); if(flag) printf("yes\n"); else printf("no\n"); } return 0; }