题解|《信息学奥赛一本通》 小木棍

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

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

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

思路：
1.因为不知道原始木棒的长度len，但是知道每根小木棍的长度，小木棒最长的时候就是一根的时候也就是长度等于所有的小木棍的长度总和sum。所以，我们可以枚举长度len。这样子就把查询问题转化成了判断该长度是否可行的问题。
2.在长度确定的同时也就确定了小木棒的数量cnt=sum/len，那么这个就可以作为合法标志的判断条件：在所有的小木棍都用完的情况下拼成了cnt个长度相等的小木棒。
3.这个时候就要思考这道题要让计算机做什么？
1.枚举长度len；
2.用之前还没有使用过的小木棍拼凑小木棒；
3.判断该长度方案是否可行。
4.考虑上面的那些状态是需要在搜索中考虑到的？
每根小木棒的长度len； 已经拼成了多少根小木棒； 每一根小木棍的状态
因为上面的sum最大是64*50（这个数字还是蛮大的），那么最坏的打算是每一个长度都要考虑进去，每一个长度的每一种拼法也都要尝试一遍，这样的话最后得出答案的话就是会需要很长时间的，更何况给出的数据是多组数据，所以我们要考虑剪枝优化。

剪枝：
1.搜索顺序的优化：我们可以按照小木棍的长度进行排序，从大到小，若填上最长的之后没有可以匹配的话，那么这个长度绝对是不合法的。（大块一定比小块需要搜索的次数少）
2.跳过相同木棒
3.如果是第一个木棒失败，则一定失败
4.如果是最后一个木棒失败，则一定失败

完整C++版AC代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 70;
int n;
int sum, length;
int stricks[N];
bool st[N];
//u为当前第几段了,cur记录当前段的长度,starct为上一次已经选过的值
bool dfs(int u, int cur, int start)
{
    if (u * length == sum) return true;
    if (cur == length)return dfs(u + 1, 0, 0);//如果发现这一段已经用完了,下一段接着来.

    for (int i = start; i < n; i++)
    {
        if (st[i]) continue;
        int l = stricks[i];
        if (cur + l <= length)
        {
            st[i] = true;
            if (dfs(u, cur + l, i + 1)) return true;
            st[i] = false;

            if (!cur) return false; // 剪枝3 如果是第一个木棒失败，则一定失败

            if (cur + l == length) return false;// 剪枝4 如果是最后一个木棒失败，则一定失败
             // 剪枝2 跳过相同木棒
            int j = i;
            while (j < n && stricks[j] == l) j++;
            i = j - 1;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio;
    cin >> n;
    sum = 0, length = 0;
    memset(st, false, sizeof st);

    for (int i = 0; i < n; i++) {
        cin >> stricks[i];
        if (stricks[i] > 50) continue;
        sum += stricks[i];
        length = max(length, stricks[i]);
    }

    sort(stricks, stricks + n); // 剪枝：优化搜索顺序
    reverse(stricks, stricks + n);

    for (int i = 0; i < n; i++)
        if (stricks[i] > 50)
            st[i] = true;

    while (true)
    {
        if (sum % length == 0 && dfs(0, 0, 0))
        {
            cout << length << endl;
            break;
        }
        length++;
    }
    return 0;
}