写在前面：
真的是服了我自己了，两道剪枝的题一道都不会就算了，今天重新打一遍Stick的时候还wa掉了两次。你是猪吗？如此蠢笨？

感觉自己wa了三次的主要原因就是没有认真检查，自己码完了就直接提交，所以因为对自己的无比自信，一道题写了好几遍都不能一次过！！！

要戒骄戒躁！！

题面

题目传送门

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
注意: 数据中可能包含长度大于50的木棒，请在处理时忽略这些木棒。
输入格式
输入包含多组数据，每组数据包括两行。
第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。
第二行是截断以后，所得到的各节木棍的长度。
在最后一组数据之后，是一个零。
输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。
输入样例：
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例：
6
5

思路

1. 因为不知道原始木棒的长度len，但是知道每根小木棍的长度，小木棒最长的时候就是一根的时候也就是长度等于所有的小木棍的长度总和sum。所以，我们可以枚举长度len。这样子就把查询问题转化成了判断该长度是否可行的问题。
2. 在长度确定的同时也就确定了小木棒的数量cnt=sum/len，那么这个就可以作为合法标志的判断条件：在所有的小木棍都用完的情况下拼成了cnt个长度相等的小木棒。
3. 这个时候就要思考这道题要让计算机做什么？
   1. 枚举长度len；
   2. 用之前还没有使用过的小木棍拼凑小木棒；
   3. 判断该长度方案是否可行。
4. 考虑上面的那些状态是需要在搜索中考虑到的？
   每根小木棒的长度len； 已经拼成了多少根小木棒； 每一根小木棍的状态。

因为上面的sum最大是64*50（这个数字还是蛮大的），那么最坏的打算是每一个长度都要考虑进去，每一个长度的每一种拼法也都要尝试一遍，这样的话最后得出答案的话就是会需要很长时间的，更何况给出的数据是多组数据，所以我们要考虑剪枝优化。

剪枝

1. 搜索顺序的优化：我们可以按照小木棍的长度进行排序，从大到小，若填上最长的之后没有可以匹配的话，那么这个长度绝对是不合法的。（大块一定比小块需要搜索的次数少）
2. 可以再小木棒的长度上考虑剪枝。最长是sum，最短是最长的小木棍的长度，而且小木棒的长度一定是sum的因数，我们可以有选择的选择长度进行dfs。
3. 在上面已经排好序的情况下，限制小木棍加入到木棒中的编号，保证加入进来的木棍的长度是递减的，（长的必须比短的先加入到正在拼凑的木棒里来）这样子的话可以避免重复搜索。
4. 记录失败的长度。若该长度的木棍拼凑失败，则该长度的一系列木棍均拼凑失败（在一大堆小木棍中可能有重复长度的木棍），此时记录最近一次尝试的长度，若该分支搜索失败，便不再向正在尝试的木棒中加入其他的相同长度的木棍。
5. 如果放第一根木棒和放最后一根木棒都失败了，那么该长度一定不合法。这个可以用反证法证明。（在最后的时候会有补充）

代码

//Author:melody
#include <bits/stdc++.h>
using namespace std;

int n,a[70];
int m,maxx,sum;
int len,cnt;
bool v[70];

bool cmp(int x,int y)
{
    return x>y;
}

/*下面的stick指的是当前拼成的第几根木棒;
下面的cab指的是当前正在拼的木棒的长度;
下面的last指的是当前正在拼的木棒可用的第一个编号;剪枝3:为了保证木棍组成木棒时的编号是递减的,避免重复*/
bool dfs(int stick,int cab,int last)
{
    if(stick>cnt)   return true;/*经过了重重剪枝,木棒拼成功了cnt个,该方案合法*/
    if(cab==len)    return dfs(stick+1,0,1);
    int fail=0;/*剪枝4:标记拼接失败的木棍的长度,避免同样长度的木棒重复搜索*/
    for(int i=last;i<=m;++i)
        if(!v[i]&&cab+a[i]<=len&&a[i]!=fail)
        {
            v[i]=true;
            if(dfs(stick,cab+a[i],i+1)) return true;
            v[i]=false;
            fail=a[i];
            if(cab==0||cab+a[i]==len)   return false;/*剪枝5:当该木棍在开头和结尾都不可以使用的时候,那么该方案就失败了*/
        }
    return false;
}

int main()
{
    while(cin>>n&&n)
    {
        sum=0,maxx=0,m=0;
        for(int i=1;i<=n;++i)
        {
            int x; scanf("%d",&x);
            if(x<=50)
            {
                a[++m]=x;
                maxx=max(maxx,a[m]); sum+=a[m];
            }
        }
        sort(a+1,a+1+m,cmp);/*剪枝1:搜索顺序的优化*/
        for(len=maxx;len<=sum;++len)/*剪枝2:省略不可用的长度*/
        {
            if(sum%len) continue;/*注意这里是mod而不是除号*/
            cnt=sum/len;
            memset(v,0,sizeof(v));/*注意一定要初始化！！！并且是在dfs前初始化。*/ 
            if(dfs(1,0,1))  break;/*因为是从小到大枚举长度,所以第一个合法的一定是最小的ans*/
        }
        printf("%d\n",len);
    }
    return 0;
} 

补充的证明：

如果木棍在第一个位置不合法的话：假设我们把该木棍用在其他的位置合法了，那么我们就可以把顺序颠倒一下，把该木棒放到第一个也是合法的，该假设与条件不符。
同理：如果木棍在最后一个位置不合法的话：假设我们把该木棍用在其他的位置合法了，那么我们就可以把顺序颠倒一下，把该木棒放到最后一个也是合法的，该假设与条件不符。

但是，放到中间的木棍就不一样了，因为这种情况也可能是该木棍和前面组成该木棒的某一个木棍不合适，所以才造就了他的不合法。在这种情况下，可能换一种方法就合适了。