拼木棍
有一些同样长的木棍，把这些木棍随意砍成几段。现在，他想把小木棍拼接成原来的的样子，但是忘记了自己开始时有多少根木棍和它们的的长度。
给出每段小木棍的长度，编程找出原始木棍的最小可能长度。
输入第一行为一个单独的整数N表示砍过以后的小木棍的总数。笫二行为N个用空格隔开的正整数，表示N根小木棍的长度，输出仅一行，表示要求的原始木棍的最小可能长度。
样例输入：
9
5 2 1 5 2 1 5 2 1
样例输出：
6
解题思路：
枚举原始木棍长度，然后验证小木棍是否能拼凑出该枚举长度的整数倍，但要充分利用题目的隐含的信息进行优化，不然会超时
优化1：原始木棍长度>=最大的小木棍长度，原始木棍长度<=小木棍长度之和
优化2：小木棍的长度之和一定是原始的木棍长度的倍数
优化3：小木棍应该由大到小去拼凑枚举出来的原始木棍长度
优化4：当每次尝试接入小木棍后，大木棍未达到要求长度时，尝试接入的下一根小木棍要和刚刚接入小木棍和长度不相等
优化5：当一个小木棍接入后，刚好达到原始木棍长度，在以后的尝试中没有必要用更小的小木棍代替这个刚接入的小木棍
根据以上解题思路完善如下程序

var
n,i,L,max,sum,j:longint;
a:array[0..100] of longint; 
visit:array[0..100] of boolean;
procedure dfs(k,now:longint);
var
i,last:longint;
begin
if (k>n) and (now=0) then 
begin 
writeln(L); 
halt;//退出整个程序 
end;
if k>n then exit;
last:=0;
for i:=1 to n do
if (not(visit[i])) and (now+a[i]<=L) and (a[i]<>last)  then
begin
visit[i]:=true; 
if (now+a[i]=L)  then 
begin
dfs(k+1,0);
visit[i]:=false;
exit;//这里的退出体现了优化5
end;
dfs(k+1,now+a[i]);
visit[i]:=false；
last:=a[i];
if now=0 then exit;
end;
end;
begin
readln(n);
i:=n;
while i>0 do
begin
read(L);
  inc(sum,L)  ;
a[i]:=L;
i:=i-1;
if L>max then max:=L;
end;
for i:=1 to n do 
for j:=i+1 to n do
if  a[i]<a[j] then //将所有木棍从大到小排序，利用优化3
begin
L:=a[i];
a[i]:=a[j];
a[j]:=L;
end;
for L:=max to sum do//枚举原始木棍长度L长度时由小到大枚举.利用优化1
if sum mod L=0 then //优化 2 
dfs(1,0);
end.