题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入输出格式
输入格式：
输入文件共有二行。
第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
输出格式：
输出文件仅一行，表示要求的原始木棍的最小可能长度
输入输出样例
输入样例#1：
9
5 2 1 5 2 1 5 2 1
输出样例#1：
6
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
［DFS＋剪枝］
考虑枚举这个长度，发现答案区间为 ［mx,sum］且 len | sum
剪枝：1.从大到小排序，对于一个大木棍 小木棍是从长到短组装的，体现在now上（不用这个now优化也行）
2.当一个小木棍接入后,当前处理的大木棍刚好达到要求的长度的话,没必要用更多的小木棍代替这个刚接入的小木棍,体现在l+a[i]==len break
3.当处理完一个大木棍之后,接入下一个大木棍的第一根小木棍用剩下的最长的小木棍，体现在l==0 break
DFS----->当前使用小木棍数，当前组装的长度，当前从大到小到了哪个木棍
//
// main.cpp
// 小木棍
//
// Created by abc on 16/8/13.
// Copyright © 2016年 abc. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=;
int n,a[N],tmp,cnt=,mx=-,sum=; bool cmp(int a,int b){
return a>b;
}
int len,ok=,vis[N]; void dfs(int tot,int l,int now){
if(ok) return;
if(tot==cnt && l==) {ok=;return;}
int last=-;
for(int i=now;i<=cnt;i++)
if(vis[i]==&&l+a[i]<=len){ //printf("t %d %d\n",i,l);
if(l+a[i]==last) continue;
last=l+a[i];
vis[i]=;
if(l+a[i]==len) dfs(tot+,,);
else dfs(tot+,l+a[i],i+);
vis[i]=;
if(l== || l+a[i]==len) break;
}
}
int main(int argc, const char * argv[]) {
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&tmp);
if(tmp<=) {a[++cnt]=tmp; mx=max(mx,tmp); sum+=tmp;}
}
sort(a+,a++cnt,cmp); for(len=mx;len<=sum;len++)
if(sum%len==){
ok=;//cout<<len<<"\n";
dfs(,,);
if(ok) break;
}
cout<<len;
return ;
}