题解 Sticks 小木棍
题目描述： 每组数据给出N根小木棍，把它们拼接成若干根长度相等的木棍，求该长度的最小值。
题解：
该题就是dfs深搜+剪枝
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int arr[68],book[68];
int len,n;
int cnt,sum,flag; //
void dfs(int stick,int cab,int last)
{
if(stick==cnt){cout<<sum/cnt<<endl;flag=1;return;}
if(flag==1)return;
if(cab==len)
{
dfs(stick+1,0,1);
return;
}
int fail=0; //剪枝（1），剪掉插入相同长度的木棍这一情况
for(int i=last;i<=n;i++)//剪枝(2),i=last 前面的木棍一定插过了，用这个来剪掉无谓的循环部分
{
if(book[i]||arr[i]+cab>len||fail==arr[i])continue;
book[i]=1;
dfs(stick,cab+arr[i],i);
book[i]=0;
fail=arr[i];
if(cab==0||cab+arr[i]==len)return; //剪枝（3）,如果此时为拼成长度为零或者刚好拼成却还得回溯，那么说明这一步怎么怎么插入都错，所以直接回溯
}
}
bool cmd(int a,int b){return a>b;} //剪枝（4）降序排序减少查找次数
int main()
{
int t;
while(cin>>n&&n)
{
sum=0;
int maxn=0;
flag=0;
for(int i=1;i<=n;i++)cin>>arr[i],sum+=arr[i],maxn=max(maxn,arr[i]);//剪枝（5），组成木棍最小为maxn，所以直接从maxn开始
sort(arr+1,arr+n+1,cmd);
for(len=maxn;len<=sum;len++)
{
if(sum%len||flag)continue;
memset(book,0,sizeof(book));
cnt=sum/len;
dfs(0,0,1);
}
}
return 0;
}
