UVA-307 Sticks

超时了好多次，一开始枚举子集，最后的做法是先算出可能的答案，
在根据dfs判断，如果可能的答案可以把所有的木棍dfs掉即为所求。
注意剪枝优化。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 vector<int> sticks;
 4 int ans; int sum_len;
 5 int vis[200]; int n;
 6 int dfs(int num, int pos, int len){
 7     if(n == num)///成功把所有木棍dfs掉
 8         return 1;
 9     for(int i = pos ; i < sticks.size() ; i++) {
10         if(vis[i]) continue;
11         if(len + sticks[i] < ans){
12             vis[i] = 1;
13             if(dfs(num + 1, i + 1, len + sticks[i])) return 1;
14             vis[i] = 0;
15             while(i+1 < sticks.size() && sticks[i] == sticks[i+1]) i++;
16             if(len == 0) return 0;/// 如果len==0 代表没有合适的 返回 0；
17         }
18         else if(len + sticks[i] == ans){
19             vis[i] = 1;
20             if(dfs(num + 1, 0, 0)) return 1;
21             vis[i] = 0;
22             return 0;
23         }
24     }
25     return 0;
26 }
27 int main()
28 {
29     while(scanf("%d", &n) && n) {
30         sticks.resize(n);
31         sum_len = 0;
32         for(int i = 0 ; i < n ; i++){
33             scanf("%d", &sticks[i]);
34             sum_len += sticks[i];
35         }
36         sort(sticks.begin(),sticks.end(),greater<int>());//从大到小排序，可以跑得更快，让dfs中的长度尽快到达ans;
37         for(int i = n ; i > 0 ; i--) {
38             if(sum_len % i == 0) {
39                 ans = sum_len / i;
40                 memset(vis, 0, sizeof(vis));
41                 if(dfs(0,0,0)) {
42                     printf("%d
", ans);
43                     break;
44                 }
45             }
46         }
47     }
48     return 0;
49 }