小木棍

题目：https://ac.nowcoder.com/acm/problem/50243

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

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

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

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

样例1
输入
9
5 2 1 5 2 1 5 2 1

输出
6

备注:
1<=N<=60

题解：这是一道搜索题，这道题的思路是在拼接木棍时，如果上一个木棍拼完，那么就从下一根最长的木棍拼起，如果没拼完，就从最大的开始拼，如果最大的接上过长就往小试探，当已经减掉了这根木棍的长度时，就不需要往下继续找了。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,tong[105],sum,a[105],MAX,ok=1,len,MIN;
int dfs(int cur,int x,int y)
{
    if(cur==0)
        ok=1;
    if(ok==1)
        return 0;
    if(y==0)
    {
        dfs(cur-1,MAX,len);
        return 0;
    }
    int i;
    for(i=x; i>=MIN&&ok==0; --i)
    {
        if(tong[i]!=0&&i<=y)
        {
            tong[i]--;
            dfs(cur,i,y-i);
            tong[i]++;
            if(y==len||y-i==0)
                break;//优化1
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    while(cin>>n&&n!=0)
    {
        memset(tong,0,sizeof(tong));
        sum=0,MAX=0,MIN=99;
        for(i=1; i<=n; i++)
        {
            cin>>a[i];
            if(a[i]>50)
                continue;
            sum+=a[i];
            tong[a[i]]++;
            MAX=max(MAX,a[i]);
            MIN=min(MIN,a[i]);
        }
        for(i=MAX; i<=sum/2; i++)//优化2
        {
            if(sum%i!=0)
                continue;
            len=i;
            ok=0;
            dfs(sum/i,MAX,i);
            if(ok)
            {
                cout<<i<<endl;
                break;
            }
        }
        if(i>sum/2)
            cout<<sum<<endl;
    }
    return 0;
}