小木棍

先看题目：https://ac.nowcoder.com/acm/problem/50243
题目描述：
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
解题思路：
这道题n不超过64，普通dfs会不行。
需要优化搜索，核心是减少搜索树的大小。方法是：1.改变搜索顺序 2.剪枝：最优化剪枝&可行性剪枝。
1.枚举长度l，满足sum % l == 0
2.将题目给的棍子的长度按照从大到小顺序排列，然后按此顺序进行深搜。为什么先拼长的呢？我们希望这个树在下面的层分叉多，而不是在上面的层分叉多。大的一放，如果不合法了很快就被搞掉了。
3.思考如果棍子放在了要拼长度的第一个位置不合法了，那么还有必要继续吗？既然拼到第一个位置都不合法，那拼到后面任何一个位置也肯定都不合法。同样的还有就是，拼在要拼长度的最后一个位置，因为我们是从大到小的顺序，那么如果大的拼上后，后面不合法了，那么如果换成小的拼成了这块长度，后面的灵活性还不如刚刚，因此也不用继续了。
4.如果一个长度不合法了，那么与它相同的长度也都不用继续了
5.因为顺序从大到小，加了个now标记当前枚举到哪个小木棍，再dfs的时候从now+1开始就行。
总结：剪枝一定要多心思心思，有些看起来无关紧要的实际上能减少大规模的搜索树。
代码：

#include<bits/stdc++.h>
using namespace std;
int n, sum;
int a[70];
bool vis[70];
bool cmp(int x, int y) {
    return x > y;
}

bool dfs(int num, int len, int rest, int now)   
{
    if((num == 0) && (rest == 0)) return true;  //一开始只写了num == 0 ，还应该rest == 0
    if(rest == 0) rest = len , now = 0; 
    for(int i = now; i < n; i++) {
        if(vis[i]) continue;
        if(a[i] > rest) continue;
        vis[i] = 1;
        if(dfs(num-1, len, rest-a[i], i+1)) return true;    
        vis[i] = 0;
        if((a[i] == rest) || (rest == len)) break;  
        while(a[i] == a[i+1]) i++;
    }
    return false;
}

int main()
{
   while(~scanf("%d",&n) && n!=0) {
       sum=0;
        memset(vis,0,sizeof(vis));
       for(int i = 0; i < n; i++) {
            scanf("%d",&a[i]);
            sum += a[i];
       }
       sort(a, a+n, cmp);
       for(int l = a[0]; l <= sum; l++) {
            if(sum%l != 0) continue;
            if(dfs(n, l, l, 0)) {
                printf("%d\n",l);
                break;
            }
       }
   }
}