神级剪枝。。。

---

首先这道题有坑点，超过50的木棍不读入。

思想肯定就是爆搜啊！但是直接的爆搜会gg。

接下来是剪枝：

1. 你当然会聪明地取能够整除的答案来枚举嘛。。

2. 这些木棍可以从大到小排序，然后从大到小凑木棍。对答案无影响。

3. 可以记录木棍的最大值和最小值，然后枚举木棍的时候就在这个区间里面弄。

4. 在每一层dfs中可以记录一个变量p，表示上一次取的木棍是哪根，从p开始枚举到更小会更快。

5. 若某组拼接不成立，且此时 已拼接的长度为0 或 当前已拼接的长度与刚才枚举的长度之和为最终枚举的答案 时，则可直接跳出循环，因为此时继续枚举其它更小的值时，显然可能情况更少，且同样凑不完。（来自@林则徐）

我抄题解来的。。。希望能够学到。

代码：

#include
    
     #include
     
      #include
      
       const int maxn = 55;int m;int a[maxn];int sum, minv = 19260817, maxv;void dfs(int length, int remain, int temp, int p){    if(remain == 0)    {        printf("%d\n", length);        exit(0);    }    for(int i = p; i >= minv; i--)    {        if(a[i] && temp + i <= length)        {            a[i]--;            if(temp + i < length) dfs(length, remain, temp + i, i);            else if(temp + i == length) dfs(length, remain - 1, 0, maxv);            a[i]++;            if(temp == 0 || temp + i == length) break;        }    }}int main(){    scanf("%d", &m);    while(m--)    {        int temp; scanf("%d", &temp);        if(temp > 50) continue;        a[temp]++;        sum += temp;        minv = std::min(minv, temp);        maxv = std::max(maxv, temp);    }    int temp = sum >> 1;    for(int i = maxv; i <= temp; i++)    {        if(sum % i == 0) dfs(i, sum / i, 0, maxv);    }    printf("%d\n", sum);    return 0;}