题面
题面翻译
乔治拿来一组等长的木棒，将它们随机的砍掉，得到若干根小木棍，并使每一节小棍的长度都不超过50个单位。然后他又想把这些木棍拼接起来，恢复到裁剪前的状态，但他忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度，每一节木棍的长度都用大于零的整数表示。
输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后具有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后。是一个零。
对于每组数据，分别输出原始木棒的可能最小长度。
感谢@锦时 提供的翻译
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0样例输出 #1
6
5思路
还是着重讲讲剪枝的思路，毕竟，搜大家都会搜。
以下把没切之前叫做木棒，切之后的单根叫做木棍。
1.搜索顺序
将所有木棍从大到小排序后枚举，降低分支数量。
其次，木棒里的小木棍加入的顺序对答案没有影响，所以按照组合的顺序枚举而不是排列。
2.可行性剪枝
先求一下所有木棍的总长度 ，然后看下枚举的长度能不能整除 ，如果不能直接舍弃即可。
然后，判断不合法的情况：
假如我往一个木棒里加入组成它的木棍们，当加到某一个时，发现这根木棒加不进去（加进去后无论如何也不能使这根木棒合法），那么和它相同长度的我也就没有必要放进去试一试了。
加入我对于这个木棒的第一根木棍放进去就不合法，那么这根木棍就无论如何也没有办法与剩下的木棍们组成木棒，所以直接回溯即可。
加入我对于这个木棒的最后一根木棍的时候就不合法，也就是说剩下的木棍们怎么也不能再拼出合法的木棒们了，也没有必要往下看了，直接回溯。
注意：后两种是可以放进去这根木棒，但会使得往后的分支无论如何也不合法，所以总共就剩这么些木棍，怎么组合也没有用了。而第一种是在放的过程中，由于受到之前已经在木棒中的木棍的影响，它无法在这根木棒中合法，但是它可能会在下一根、下下根木棒中合法，有希望，所以要接着搜下去。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 70;
int n;
int w[N], sum, length;
bool st[N];
bool DFS(int u, int s, int start)
{
if(u * length == sum) return true;
if(s == length) return DFS(u + 1, 0, 0);
// 剪枝 3-1 按照组合方式枚举
for(int i = start; i < n; ++i)
{
if(st[i]) continue;
if(s + w[i] > length) continue;
st[i] = true;
if(DFS(u, s + w[i], i + 1)) return true;
st[i] = false;
// 剪枝 3-3 这根要拼的木棒第一个木棍就不行没必要看
if(!s) return false;
// 剪枝 3-4 这根要拼的木棒最后一个木棍不行也没必要看
if(s + w[i] == length) return false;
int j = i;
// 剪枝 3-2 相同长度的不行的没必要重复看
while(j < n && w[j] == w[i]) j++;
i = j - 1;
}
return false;
}
int main()
{
while(cin >> n, n)
{
memset(st, 0, sizeof(st));
sum = 0;
for(int i = 0; i < n; ++i)
{
cin >> w[i];
sum += w[i];
}
sort(w, w + n);
reverse(w, w + n); // 剪枝2 从大到小枚举，减少分支
length = 1;
while(true)
{
// 当前拼的这根木棒的编号，当前拼的这根木棒的长度，从第几根木棍开始拼
if(sum % length == 0 && DFS(0, 0, 0)) // 剪枝1 只有能整除才是合法的
{
cout << length << endl;
break;
}
length++;
}
}
return 0;
}