【HDOJ】1455 Sticks

DFS。搜索以棍数为条件循环搜索较好，这样不会超时。
 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 #define true  1
 6 #define false 0
 7 #define MAXN  70
 8 
 9 int alen;
10 int parts[MAXN];
11 char visit[MAXN];
12 int n, m;
13 
14 int dfs(int beg, int cnt, int len) {
15     int i;
16 
17     if (len == 0) {
18         ++cnt;
19         if (cnt+1 == m)
20             return true;
21 
22         for (i=0; i<n; ++i)
23             if ( !visit[i] )
24                 break;
25 
26         visit[i] = 1;
27         if ( dfs(i+1, cnt, alen-parts[i]) )
28             return true;
29         visit[i] = 0;
30 
31         return false;
32     }
33 
34     for (i=beg; i<n; ++i) {
35         if (visit[i] || parts[i]>len)
36             continue;
37         if (i && parts[i]==parts[i-1] && !visit[i-1])
38             continue;
39         visit[i] = 1;
40         if ( dfs(i+1, cnt, len-parts[i]) )
41             return true;
42         visit[i] = 0;
43     }
44 
45     return false;
46 }
47 
48 int comp(const void *a, const void *b) {
49     return *(int *)b - *(int *)a;
50 }
51 
52 int main() {
53     int sum;
54     int i;
55 
56     while (scanf("%d", &n)!=EOF && n) {
57         sum = 0;
58         for (i=0; i<n; ++i) {
59             scanf("%d", &parts[i]);
60             sum += parts[i];
61         }
62         qsort(parts, n, sizeof(int), comp);
63         m = n+1;
64         while (m > 1) {
65             --m;
66             if (sum%m)
67                 continue;
68             alen = sum/m;
69             if (parts[0] > alen)
70                 continue;
71             memset(visit, 0, sizeof(visit));
72             if ( dfs(0, 0, alen) )
73                 break;
74         }
75         printf("%d
", alen);
76     }
77 
78     return 0;
79 }