<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 $50$ 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过 $64$ 的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 $50$。

输入样例：

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例：

6
5

思路

洛谷题目链接
以下为洛谷的优化（优化更多）
剪枝优化：

1. 每一段的长度一定是所有木棍总长的因数
2. 最优化剪枝：
   优先枚举点数少的分支，即把所有数按从大到小枚举
3. 排除等效冗余：
   1. 按下标从小到大枚举，把一根木棒中的所有木棍顺序只枚举一次
   2. 如果当前木棍加到当前木棒中失败了，那么直接掠过所有相同长度的点
      反证法：
      假设相同的木棍在同一位置摆放时成功了
      如果当前木棒不能放在这里，则当前木棒一定放在后面，相同长度的木棍代替当前木棍
      交换两个木棍，使得当前木棍在原位置成功了，矛盾
      故相同长度的木棍若有一个不成立，则所有的木棍都不成立
   3. 如果一个木棍在第一个位置摆放时失败了，则一定失败
      反证法：
      假设当前木棍放在后面成功了
      先把当前木棍（移到后面的位置的木棍）移到最前方，并且不会影响答案
      再把当前木棍（移到后面的位置的木棒）和原来的位置交换，使得当前木棍移到前面后成功了，矛盾
      所以如果一个木棍在第一个位置摆放时失败了，则一定失败
   4. 如果一个木棍在最后一个位置摆放时失败了，则一定失败
      证明类似$3.3$
4. 跳过一个数我们可以直接删除提高效率，回溯时加回这个点即可，这里我用的是双向链表

代码

/*
  1.length | sum
  2.优先搜索顺序：从大到小枚举
  3.排除等效冗余：1) 按照组合数方式枚举。
  2) 如果当前木棍加到当前棒中失败了，则直接略过后面所有长度相等的木棍
  3) 如果是木棒的第一根木棍失败了，则一定失败
  4) 如果是木棒的最后一根木棍失败了，则一定失败
 */
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 70;
int n;
int a[N];
bool used[N];
int l[N],r[N];
int length,sum;
bool dfs (int u,int len,int start) {
    if (u * length == sum) return true;
    if (len == length) return dfs (u + 1,0,1);
    for (int i = start;i <= n;i = r[i]) {    //剪枝3-1
        if (used[i] || len + a[i] > length) continue;
        used[i] = true;
        l[r[i]] = l[i],r[l[i]] = r[i];
        if (dfs (u,len + a[i],r[i])) return true;
        l[r[i]] = r[l[i]] = i;
        used[i] = false;
        if (!len || len + a[i] == length) return false; //剪枝3-3&3-4
        int j = i;
        while (j <= n && a[j] == a[i]) j++; //剪枝3-2
        i = j - 1;
    }
    return false;
}
int main () {
    sum = 0;
    cin >> n;
    r[0] = 1;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        sum += a[i];
        l[i] = i - 1,r[i] = i + 1;
    }
    sort (a + 1,a + 1 + n,[](int x,int y) {
        return x > y;
    }); //剪枝2
    length = 0;
    while (true) {
        length++;
        if (sum % length) continue; //剪枝1
        if (dfs (1,0,1)) {
            cout << length << endl;
            break;
        }
    }
    return 0;
}