POJ 1011 Sticks

现在有n根木棍，然后需要把它们拼成同样长度的木棍，问满足这个条件的最短的长度是多少？

搜索一下，显然长度之和应该能整除木棍数量，用这个数去看木棍能不能达成

有几个剪枝，先用桶排序，然后每次算的时候从大向小装，记一下装到的长度l，如果没有拼好这个木棍就接着l开始，如果拼好了就开始新的木棍从最大的那个长度开始。（想一想觉得还是很妙的）还有一个神奇的剪枝就是说如果放入了这个木棍，使这个木棍刚好拼好一个完整的棍或者这个木棍使第一个棍，那就不用再往下枚举长度了。因为枚举这个木棍之后的DFS已经把往下枚举的情况考虑过了！
（说的有点啰嗦了

\#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define inf 0x3f3f3f3f
const int N = 100;
int S[N],sum,max=-inf,flag,min=inf,n,nn;
inline int dfs(int cnt,int now,int sum,int m){
    if(flag) return flag;
    if(cnt==0){
        printf("%d\n",sum);
        flag=1;
    }
    if(now==sum){
        dfs(cnt-1,0,sum,max);
    }
    for(int i=m;i>=min;--i){
        if(!S[i]||i+now>sum) continue;
        S[i]--;
        dfs(cnt,now+i,sum,i);
        S[i]++;
        if(now==0||now+i==sum) return 0;
    }
}
int main (){
    while(scanf("%d",&n)&&n){
        memset(S,0,sizeof(S));
        sum=flag=0;
        for(int i=1;i<=n;++i){
            int x;
            scanf("%d",&x);
            if(x<=50){
                ++nn;
                min=std::min(min,x);
                max=std::max(max,x);
                S[x]++;
                sum+=x;
            }
        }
        n=nn;
        for(int i=min;i<=sum;++i){
            if(sum%i!=0) continue;
            dfs(sum/i,0,i,max);
        }
    }
    return 0;
}