【題意】：喬治拿來一組等長的木棒，將它們隨機地砍斷，使得每一節木棍的長度都不超過50個長度單位。然后他又想把這些木棍恢復到為裁截前的狀態，但忘記了初始時有多少木棒以及木棒的初始長度。請你設計一個程序，幫助喬治計算木棒的可能最小長度。每一節木棍的長度都用大于零的整數表示。

【隨筆】：這道題很早之前就過了，這幾天看回之前的代碼，覺得以前的代碼寫得太爛了，而且那個代碼風格也不好看，于是決定再重寫一邊，順便把uva的也過了。這次重寫比之前的代碼加多了一個重要的剪枝，最后在uva上以0.2s過了。

【題解】：不得不說，這道題出得非常好，特別是uva那里的大數據（poj的數據太水了），對于剪枝能力要求很高。下面說下幾個重要的剪枝：
1.把所有木棍的長度從大到小排列，組合木棒時優先使用長的木棍，這樣可以加快組合速度，并且對后面的剪枝有幫助。
2.木棒的長度一定是大于等于最長木棍的長度并且小于等于所有木棍長度的和，這個很容易證明。
3.木棒的長度一定是所有木棍長度的和的約數，這個也很容易證明。
4.在某一個木棒的組合過程中，對于當前的木棍stick[i]，如果stick[i-1]沒有被組合并且stick[i] == stick[i-1]，那么不用考慮stick[i]，顯然stick[i]最終也不會被組合。
5.如果此次是在嘗試第i個木棒的第一段，假設stick[j]為當前可以被使用的最長的木棍，如果此次組合失敗，直接退出搜索，即退回到對第i-1個木棒的搜索。試想：失敗說明現在使用stick[j]是不可行的，那么以后無論什么時候使用stick[j]都是不可行的，因為以后再處理stick[j]時可使用的木棍一定是當前可使用的木棍的子集，在更多木棍選擇的情況下都不能組合成功，那么，在更少木棍選擇的情況下一定不能組合成功。

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "functional"
 6 using namespace std;
 7 #define maxn 65
 8 int n, sum, goal;
 9 int stick[maxn];
10 bool visit[maxn];
11 
12 bool cmp(const int &a, const int &b) {
13     return a > b;
14 }
15 
16 bool dfs(int now, int index, int cnt) {
17     if(goal * cnt == sum) return true;
18     for(int i = index; i < n; i++) {
19         if(visit[i] || (i && !visit[i-1] && stick[i] == stick[i-1])) continue;
20         if(now + stick[i] == goal) {
21             visit[i] = true;
22             if(dfs(0, 0, cnt + 1)) return true;
23             visit[i] = false;
24             return false;
25         } else if(now + stick[i] < goal) {
26             visit[i] = true;
27             if(dfs(now + stick[i], i + 1, cnt)) return true;
28             visit[i] = false;
29             if(now == 0) return false;
30         }
31     }
32     return false;
33 }
34 
35 int solve() {
36     sort(stick, stick + n, cmp);
37     for(goal = stick[0]; goal < sum; goal++) {
38         if(sum % goal != 0) continue;
39         memset(visit, false, sizeof(visit));
40         if(dfs(0, 0, 0)) break;
41     }
42     return goal;
43 }
44 
45 int main() {
46     while(~scanf("%d", &n)) {
47         if(!n) break;
48         sum = 0;
49         for(int i = 0; i < n; i++) {
50             scanf("%d", &stick[i]);
51             sum += stick[i];
52         }
53         printf("%d\n", solve());
54     }
55     return 0;
56 }