题目描述

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入描述:

第一行为一个单独的整数N表示砍过以后的小木棍的总数。第二行为N个用空格隔开的正整数，表示N根小木棍的长度。

输出描述:

输出仅一行，表示要求的原始木棍的最小可能长度。

示例1

输入
9
5 2 1 5 2 1 5 2 1
输出
6
备注:

思路1（先不考虑剪枝）

管原始木棍叫大棍，砍过以后的小木棍叫小棍以作区分好了。。。

总体采用枚举所有可能解然后dfs搜索的思路。

枚举：输入每根小棍长度a[i]的时候记录一下所有小棍的长度和sum。从最长的那根小棍a[0]开始直到长度和sum枚举每一种可能的大棍长度。

dfs：根据思路设计dfs参数 从当前的now号小棍开始，往后遍历一遍所有小棍，将它们依次拼接上去。（每次都取剩余小棍中最长的那根开始拼接，即先对所有小棍的长度a[n]进行一次排序）

若当前拼接的长度达到了我们枚举假设出来的大棍长度 ，就进行下一根小棍的拼接

若当前小棍已经使用过则跳过这跟小棍。（需要一个visited数组记录使用情况）

直到我们手里的小棍全部用完&&正在拼接的这跟大棍刚刚好拼完 (即剩余长度为0)就返回true

综上，我们dfs的参数需要有：当前准备拼接的now号小棍、这趟搜索假设出来的大棍长度len、记录每次搜索时手里剩下的小棍数量num、当前正在拼接的这根大棍的剩余长度rest（参考上述思路中下划线部分）

思路2（剪枝）

上述思想已经可以做出正确的答案了。但是不考虑剪枝的话这题会TLE。所以我们必须做出一些剪枝策略：

  1. 我们知道小棍是由n根大棍砍开得到的。由于这个n是一个正整数，所以大棍的长度一定是总长度的因子。即枚举答案的时候，若当前枚举出的数值不能被总长度整除，说明这不是一个可能的答案。直接跳过，都不需要进dfs了。
  2. 若将当前正在尝试的这根小棍放置在大棍打头的位置发现不可行，说明当前假设出的大棍长度是不可行的。因为这根小棍总要被用上，而你放在第一个位置已经不可行了！（第一个位置的限制条件是最宽松的，因为此时剩余的长度最宽）放后面就更不可行了！此时直接结束dfs，不需要再试探下去了！
  3. 同理，若当前小棍放在大棍末尾的位置刚好能放下但后续的拼接无法恰好拼上，说明当前假设出来的大棍长度不可行（因为这根小棍总要被放下！！！）跳过这个len
  4. 当前长度的小棍试探过后，与这一根相同长度的棍子就不用再试了。

    ac代码：

    #include<bits/stdc++.h>
using namespace std;
int n;
int v[65], a[65];
bool cmp(int b, int c){
return b > c;
}
bool dfs(int num, int rest, int len, int now){
//剩下的小棍子数量，当前大棍剩下的长度
//枚举的大棍长度,拼接当前大棍的第now根小棍子
if(0 == num && 0 == rest)  //小棍子全部拼完且没有剩余长度
    return true;
if(0 == rest){             //拼下一根大棍
    rest = len;
    now = 0;
}
for(int i = now; i < n; i++){
    if(v[i]) continue;       //已使用
    if(a[i] > rest) continue;//这根小棍大于剩余长度,放不下，pass
    v[i] = 1;
    if(dfs(num - 1, rest - a[i], len, i))
        return true;
    v[i] = 0;//回溯
    if(rest == len || rest == a[i])
        break;             //第一根或最后一根小棍不行，说明当前枚举的len行不通
    while(a[i] == a[i + 1])
        i++;               //与当前长度一致的小棍就不需要再尝试了
}
return false;
}
int main(){
cin>>n;
int sum = 0, i;
for(i = 0; i < n; i++){
    cin>>a[i];
    sum += a[i];
}
sort(a, a + n, cmp);         //从最长的小棍子开始拼接
for(i = a[0]; i <= sum; i++){//从最长的小棍长度开始枚举
    if(sum % i != 0) continue;//假设的大棍不能被总长整除，不可行！
    if(dfs(n, i, i, 0)) break;
}
cout<<i<<endl;
return 0;
}
    就是这样。BTW：dfs不要忘记回溯：恢复当前小棍未使用的状态