Problem Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output file contains the smallest possible length of original sticks, one per line.
SampleInput
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0 SampleOutput
6
5
題意就是給你一堆不同長度的木棍，要你用他們拼成長度相等的木棍，輸出最短且滿足要求的木棍長度。
就直接從0開始搜嘛，判斷長度相同就輸出，好了就這樣，送出，TLE。
=7=那麼看來不能直接搜尋，如何優化呢，當然就是判斷一些條件剪枝，首先是搜尋範圍，根據題意有原始長度肯定比現在最長的要長，而且能被現在總長除盡，原始長度最長肯定就是總長度（隻有一根木棍），其次就是對于同一個長度的木棍，隻嘗試一次，一次不成功便不需要嘗試第二次，然後就依次dfs就行了。
代碼：
1 #include <iostream>
2 #include <string>
3 #include <cstdio>
4 #include <cstdlib>
5 #include <sstream>
6 #include <iomanip>
7 #include <map>
8 #include <stack>
9 #include <deque>
10 #include <queue>
11 #include <vector>
12 #include <set>
13 #include <list>
14 #include <cstring>
15 #include <cctype>
16 #include <algorithm>
17 #include <iterator>
18 #include <cmath>
19 #include <bitset>
20 #include <ctime>
21 #include <fstream>
22 #include <limits.h>
23 #include <numeric>
24
25 using namespace std;
26
27 #define F first
28 #define S second
29 #define mian main
30 #define ture true
31
32 #define MAXN 1000000+5
33 #define MOD 1000000007
34 #define PI (acos(-1.0))
35 #define EPS 1e-6
36 #define MMT(s) memset(s, 0, sizeof s)
37 typedef unsigned long long ull;
38 typedef long long ll;
39 typedef double db;
40 typedef long double ldb;
41 typedef stringstream sstm;
42 const int INF = 0x3f3f3f3f;
43
44 int s[500050];
45 bool vis[500050];
46 int sum,n;
47
48 bool dfs(int pos, int res, int len){
49 if(pos == 0 && res == 0)
50 return true;
51 if(!res)
52 res = len;
53 for(int i = n - 1; i >= 0; i--){
54 if(vis[i] || s[i] > res)
55 continue;
56 vis[i] = true;
57 if(dfs(pos - 1, res - s[i], len))
58 return true;
59 vis[i] = false;
60 if(res == s[i] || res == len) //判斷是否嘗試過
61 return false;
62 }
63 return false;
64 }
65
66 int main(){
67 ios_base::sync_with_stdio(false);
68 cout.tie(0);
69 cin.tie(0);
70 while(cin >> n && n){
71 sum = 0;
72 for(int i = 0; i < n; i++){
73 cin >> s[i];
74 sum += s[i];
75 }
76 sort(s, s+n);
77 int i;
78 for(i = s[n - 1]; i <= sum/2;i++){ //從最大長度開始dfs
79 if(sum % i) //小于總長度則dfs嘗試
80 continue;
81 MMT(vis); //每次dfs前記得清空标記
82 if(dfs(n,i,i)){
83 cout << i << endl;
84 break;
85 }
86 }
87 if(i > sum/2) //大于長度一半，則不可能被分成多個木棍，肯定隻能由一根木棍構成
88 cout << sum << endl;
89 }
90 return 0;
91 }