小木棍

链接：https://ac.nowcoder.com/acm/problem/50243

题目描述：

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入描述：

第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二行为N个用空格隔开的正整数，表示N根小木棍的长度。

输出描述：

输出仅一行，表示要求的原始木棍的最小可能长度。

solution：

1.可以深搜寻找最短长度，从现有的小木棍的最大长度开始，如果找到那就跳出循环，没找到，就一直找直到小木棍的总长。中间存在一些可以不遍历的情况，当总长不是假设长度的整数倍时，那么这种情况肯定不成立，因为原始木棍都是一些长度相等的木棍，只有整数倍才可以实现。
2.当放上去的木棍是当前要拼的木棍的第一根时，如果不能组成一根假设长度木棍，那么这种情况肯定不成立
3.当放上去的木棍是当前要拼的中间位置，如果不能组成一根假设长度木棍，那么跟它等长的木棍也不行，直接从下一根不等长的木棍开始找
4.当放上去的木棍是当前要拼的最后位置，如果不能组成假设长度的木棍，那么此情况不成立

#include<bits/stdc++.h>
using namespace std;
int num,a[65],s=0,vis[65];
bool cmp(int a,int b)
{
    return a>b;
}
bool dfs(int n,int len,int rest,int now)
{
    if(n==0&&rest==0)return true;
    if(rest==0){rest=len;now=0;}
    for(int i=now;i<num;i++)
    {
        if(vis[i]||a[i]>rest)continue;
        vis[i]=1;
        if(dfs(n-1,len,rest-a[i],i))
            return true;
        vis[i]=0;
        if(len==rest)break;
        if(rest==a[i])break;
        while(a[i]==a[i+1])i++;
    }
    return false;
}
int main()
{
    cin>>num;
    for(int i=0;i<num;i++)
    {
        cin>>a[i];
        s+=a[i];
    }
    memset(vis,0,sizeof(vis));
    sort(a,a+num,cmp);
    for(int i=a[0];i<=s;i++)
    {
        if(s%i==0)
        {
            if(dfs(num,i,i,0))
            {
                cout<<i;
                break;
            }
        }
    }
}