题意：你有一组等长的木棒，现在你随机地砍断它们得到若干根小木棍，且每一根小木棍的长度小于等于 。现在你想把这些木棍拼接起来恢复到初始状态，但是你忘记了初始时有多少根木棒和木棒长度，问木棒的可能最小长度，保证所有所给的长度均为大于 的整数。
解析：一道搜索模板题。我们首先枚举木棒的长度 ，它应该是木棍长度总和 的约数，然后再搜索每一根木棒应该用哪些木棍拼接起来。每一个状态包括三个参数：，分别记录正在拼第几根木棒，正在拼的木棒已经拼了多长，上一根用来拼的小木棍，每个状态枚举未用的木棍中选择一个尝试来拼接来递归到新状态，直到拼完所有 根。
现在我们需要考虑如何剪枝。目前常用的剪枝方法有这几种：
-
优化搜索顺序
就是将搜索的顺序变成能让程序跑得更快的顺序，一般对其进行有序化处理；
-
排除等效冗余
若在搜索中产生了分支，其中有几条分支产生的结果相同或产生的效果相等时，只用搜索其中一条分支就过了，不必搜索其他分支；
-
可行性剪枝
若在进行搜索一条分支时，如果发现这条分支无法到达递归边界，直接回溯；
-
最优性剪枝
在剪枝过程中，如果发现目前的费用已经大于已搜索到的最优费用，直接回溯；
-
记忆化
对于每次搜索到的结果进行存储，避免搜索到重复或多余的结果。
这道题我们来考虑以上剪枝：
-
首先考虑能否优化搜索顺序。我们把小木棍长度从大到小排序，即开始尽可能拼更长的木棍，这样能更快拼完；
-
接着是排除等效冗余。可以分析出以下几点相同的分支：
- 任意拼两根小木棍时，先后顺序是和结果无关的。我们可以限制只搜索其中一种顺序，即规定小木棍的拼接顺序按照小木棍长度递减，这里利用了拼接顺序的等效性；
- 我们记录了上一根用来拼接的小木棍 ，如果用它拼接搜索失败，我们就不用拼接和这根小木棍长度相同的小木棍，这里利用了木棍等长的等效性；
- 如果在当前拼的木棒中，尝试拼入的第一根木棍的递归分支就搜索失败，那么直接判定当前分支失败。因为在拼入这根木棍前所有待拼的木棒都是空的，不管选择拼哪根木棒都会失败，这里利用了空木棒的等效性；
- 如果在当前拼的木棒中，拼入这跟木棍恰好能拼接完整这跟木棒，但接下来拼接剩余原始木棒的递归分支失败，那么直接返回当前分支失败。因为用 根木棍恰好拼完当前木棒必然比用多根木棍拼完当前木棒更好，且两者是等效的。这里利用了贪心思想。
-
接着是可行性剪枝。我们不能在拼接过程中直接判断是否可行，所以没用到这个方法；
-
然后是最优性剪枝。这道题并没有求最优方案，也不会用到这个方法；
-
最后是记忆化。这道题不会搜索到之前有过的状态，所以不必记忆化。
综上，我们用前 个剪枝即可通过这道题。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[101],d[101],n,cnt,len,sum,v;
bool dfs(int num,int now,int last)
{
if(num>cnt)
return true;
if(now==len)
return dfs(num+1,0,1);
int flag=0;//用于记录长度相同的木棍，剪枝2.2
for(int i=last;i<=n;i++)//剪枝2.1
{
if(!d[i]&&now+a[i]<=len&&flag!=a[i])
{
d[i]=1;
if(dfs(num,now+a[i],i+1))
return true;
flag=a[i];
d[i]=0;
if(now==0||now+a[i]==len)//剪枝2.3，2.4
return false;
}
}
return false;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
v=max(v,a[i]);
}
sort(a+1,a+n+1);//剪枝1
reverse(a+1,a+n+1);
for(len=v;len<=sum;len++)//枚举长度
{
if(sum%len)
continue;
cnt=sum/len;//多少根木棒
memset(d,0,sizeof(d));
if(dfs(1,0,1))
break;
}
printf("%d",len);
return 0;
}
