HDU-1518 Square(DFS)

Square

Time Limit : 10000/5000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 20 Accepted Submission(s) : 12

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

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

University of Waterloo Local Contest 2002.09.21

此题需要优化时间，避免超时。。优化时间技巧可以学习。。。。。。。。。

 1 #include <stdio.h>
 2 #include<string.h>
 3 int a[10000];
 4 int vist[10000];
 5 int sum;
 6 int l;
 7 int n;
 8 int flag;
 9 void Dfs(int t, int len, int index)
10 {
11     
12 
13     if (t == 5)
14     {
15         flag = 1;
16         return ;
17     }
18 
19     if (len == l)
20     {
21         Dfs(t + 1, 0, 0);
22         if (flag)//优化时间
23         {
24             return ;
25         }
26     }
27 
28     for (int i = index; i < n; i++)//从index开始优化时间
29     {
30         if (vist[i]==0 && a[i] + len <= l)
31         {
32             vist[i] = 1;
33             Dfs(t, a[i] + len, i + 1);
34             if (flag)//优化时间
35             {
36                 return;
37             }
38             vist[i] = 0;
39         }
40     }
41 }
42 
43 int main()
44 {
45     int i,t;
46     scanf("%d", &t);
47     while (t--)
48     {
49         
50         sum = 0;
51         scanf("%d", &n);
52         for (int i = 0; i < n; i++)
53         {
54             scanf("%d", &a[i]);
55             sum += a[i];
56         }
57         
58         if (sum % 4 != 0)//简答的优化
59         {
60             puts("no");
61             continue;
62         }
63 
64 
65         l = sum / 4;
66 
67        
68         for (i = 0; i < n; i++)//有比边长大的边就不行
69         {
70             if (a[i] > l)
71             {
72                 break;
73             }
74         }
75         if (i != n)
76         {
77             puts("no");
78             continue;
79         }
80        memset(vist, 0, sizeof(vist));
81         flag = 0;
82         Dfs(1, 0, 0);
83         if (flag)
84         {
85             puts("yes");
86         }
87         else
88         {
89             puts("no");
90         }
91     }
92     return 0;
93 }