hdu 1518 Square (dfs)

Square

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7090 Accepted Submission(s): 2298

Problem 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

4 1 1 1 1

5 10 20 30 40 50

8 1 7 2 6 4 4 3 5

Sample Output

yes

Source

University of Waterloo Local Contest 2002.09.21

Recommend

LL | We have carefully selected several similar problems for you: 1732 1401 1043 1226 1180

 1 //578MS    328K    998 B    G++
 2 /*
 3 
 4     题意：
 5         问给出的值能否均分成四分。
 6         
 7     dfs:
 8         排序后实际上大大缩短了搜索时间 
 9 
10 */
11 #include<iostream>
12 #include<algorithm>
13 using namespace std;
14 int a[50],vis[50];
15 int n,s;
16 int cmp(int x,int y)
17 {
18     return x>y;
19 }
20 int dfs(int pos,int t,int cur)
21 {
22     if(t==4) return 1;
23     for(int i=pos;i<n;i++)
24         if(!vis[i]){
25             vis[i]=1;
26             if(cur+a[i]==s){
27                 if(dfs(0,t+1,0)) return 1;
28             }else if(cur+a[i]<s){
29                 if(dfs(i+1,t,cur+a[i])) return 1;
30             }
31             vis[i]=0;
32         }
33     return 0;
34 }
35 int main(void)
36 {
37     int t;
38     scanf("%d",&t);
39     while(t--){
40         memset(a,0,sizeof(a));
41         scanf("%d",&n);
42         s=0;
43         for(int i=0;i<n;i++){
44             scanf("%d",&a[i]);
45             s+=a[i];
46         }
47         sort(a,a+n,cmp);
48         if(s%4 || a[0]>s/4){
49             puts("no");
50         }else{
51             s/=4;
52             memset(vis,0,sizeof(vis));
53             if(dfs(0,0,0)) puts("yes");
54             else puts("no");
55         }
56     }
57     return 0;  
58 }