小木棍

题目链接：https://ac.nowcoder.com/acm/problem/50243

题目描述

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

输入描述

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

输出描述

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

示例

输入

9
5 2 1 5 2 1 5 2 1

输出

6

分析

本题采用深搜加剪枝的算法。
首先，N个小木棍的长度均为整数，因此原长度必为整数(若原长为小数，则进行分割必产生小数长度的木棍)。
题目要求找出可能的最小木棒长度，所以我们可以想到通过深搜一个数一个数的去验证，但显然单纯深搜会相当耗时，最多有
60个木棍，不优化的话每确定一个木棍都要遍历60次，总共确定60次，且仅仅完成一个长度的试探。
因此，我们就要通过一些优化技巧和剪枝来提高效率。

优化技巧：

• 深搜时从长度大的木棍开始试探，可以减小搜索树的规模。
• 深搜函数多设置一个参数。我们木棍长度由大到小的顺序来试探的，在一个尚未拼完整的木棒中，下一层要试探的木棍必然是比该层短的木棍(我们将存储木棍长度的数组排序)，传入该层木棍的下标，下一层从该下标开始遍历，可以减少循环次数。

剪枝：

• 所有木棍的长度均小于等于原长，所以我们试探的下界为所有木棍长度的最大值。
• 求得木棍长度总和，对于一个可能的原长值，若总和是该值的整数倍，则有可能(前面已述原长必为整数，总和除以该值即为原长)，否则直接跳过。
• 某一层某木棍试探失败后，若该木棍试探位置位于木棒首部或尾部，则直接结束该层，回退到上一层换值试探。因为此时试探的情况为：已经完整的拼好了几个木棒，没有拼一半的木棒，继续在该层换小长度的木棍再试探没有意义(必失败)，问题必然出自前面。

以上各方面实现到位，即可AC。

AC代码

---

#include <iostream>
#include <algorithm>
#include <cstring>
#include <functional>
using namespace std;
int N;
int a[60];      //存木棍长度
bool visited[60];
bool dfs(int num, int len, int res, int now) //剩余多少木棍 假设的木棍长度 
{                                            //当前正拼接木棍的长度 下一层递归的起始搜索序号
    if (res == 0 && num == 0)
        return true;
    if (res == 0)
    {
        res = len;
        now = 0;
    }
    for (int i = now; i < N; i++)
    {
        if (visited[i])
            continue;
        if (a[i] > res)
            continue;
        visited[i] = true;
        if (dfs(num - 1, len, res - a[i], i + 1))
            return true;

        visited[i] = false;
        if (a[i] == res || res == len)  //分别表示木棒尾端 和木棒头部拼接失败
            return false;
        while (a[i] == a[i + 1])        //越过长度相同的木棍
            i++;
    }
    return false;
}
int main()
{
    int sum = 0;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    sort(a, a + N, greater<int>());
    for (int i = a[0]; i <= sum; i++)
    {
        if (sum % i == 0 && dfs(N, i, i, 0))
        {
            cout << i << endl;
            break;
        }
    }
    return 0;
}