从看到有佬友在L站发题解，我也来试试，督促自己一下继续讨论：
读题
P1120 小木棍 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
给 n 个小木棍的长度 a_i ，满足 1 \leq a_{i} \leq 50 , n \leq 650 ，它们之间可以任意拼接，现在要让它们拼接后的长度相同，求这个相同长度的最小值。
例如：
9
5 2 1 5 2 1 5 2 1
其中最小的长度是6，分别由3个 5 1 和一个2 2 2拼成。
题目说是搜索题。
思路
这题看起来简洁易懂，但是实际操作起来却比较繁琐，我最早不信邪，使用贪心来尝试，结果不行，还是只能老老实实去写搜索。
首先分析一下题目中隐藏的数学性质：最终相同长度的木棍的数量范围是确定的，从1~n，那么木棍长度的可能取值其实是有限的，可以容易得出：长度一定能被所有木棍长度之和sum整除，且这个长度一定 ≥ 木棍长度 a_i 的最大值。
因此，我们可以把答案的可能取值都先求出来，然后从小到大依次尝试能否合成。
至于如何判断能否合成，我最早使用贪心的思路是：把合成木棍看作“填充”，刚好填满则算合成一根。每一次从最大能被填入剩余空间的木棍开始填入，如果能顺利填完当然就是可以满足条件了，直接结束，返回这个长度就是最小的；如果遇到所有剩余的木棍都无法填入就说明不行，继续尝试下一个最小长度。
但是这个贪心算法有漏洞，判断为无法填入的情况，有可能有别的解。
反例：3 4 7 8 18 20
贪心45分
总结
#include <bits/stdc++.h>
using namespace std;
int fac[50]{0};
int fac_cnt = 0;
int max_num = 0;
int bucket[51]{0}; // 统计每个长度的个数
int n;
int sum = 0;
bool is_valid(int p)
{
cout << p << endl;
int bucket_copy[51]{0};
for (int i = 0; i <= max_num; i++)
{
bucket_copy[i] = bucket[i];
}
for (int i = 0; i < sum / p; i++)
{
int max_num_copy = max_num;
int pp = p;
while (pp > 0)
{
if (bucket_copy[max_num_copy] == 0 ||
max_num_copy > pp) // 查找最低能被减的值
{
do
{
if (max_num_copy == 0)
{
cout << "FAILED\n";
return false;
}
max_num_copy--;
} while (bucket_copy[max_num_copy] == 0 || max_num_copy > pp);
}
pp -= max_num_copy;
bucket_copy[max_num_copy]--;
cout << max_num_copy << '\n';
}
}
return true;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int ai;
cin >> ai;
max_num = max(ai, max_num);
sum += ai;
bucket[ai]++;
}
// 对sum求因子
for (int i = max_num; i <= sum; i++)
{
if (sum % i == 0) // 整除
{
fac[fac_cnt++] = i;
}
}
for (int i = 0; i < fac_cnt - 1; i++)
{
if (is_valid(fac[i]))
{
cout << fac[i] << endl;
system("pause");
exit(0);
}
}
cout << sum << endl; // 都不满足则是sum
system("pause");
return 0;
}
于是我还是老老实实地写搜索了，搜索其实思路也不难，我这边用的是dfs。每次合成木棍，写一个循环从长到短选择合适的木棍填入，然后进入下一状态，如果所有长度的木棍都试了也不行，则返回false；如果所有的木棍都合成完毕才返回true。
难在如何对搜索进行剪枝优化。剪枝操作就是在某种状态下，已经能够确定结果是什么了，就停止“递”，马上“归”的操作。
先要明白一个结论：如果需要某个长度，比如说5，而此时你还有2、3，那么选择5可以看作是选择2、3的“上位”，因为2、3合起来完全可以替代5，而反过来就不行了。因此我们要优先选择5，后面再尝试2、3，这就是从大往小搜索的原因。
这里就写几个最关键的优化，至于其他无关痛痒的优化，：
- 使用桶来装木棍的长度。桶的好处在于，既能按从长到短的顺序取出木棍，又能充当
vis数组，“记录”已经访问的长度的信息。 - 每次查找可用木棍的时候，从上次查找到的地方继续，不用从头开始查找。因为如果填入比上次更长的木棍可以的话，就应该优先选，这样上次不应选小的木棍。
- 如果在剩下的长度和当前木棍的长度一样，但发现这根填进去返回
false，直接跳出循环，判断这个分支为false，因为这已经是最优的选择了，如果选择用更小的木棍来补成这个长度肯定更不行。 - 如果一点都没填且发现失败了，也直接返回
false，道理和上面一样，最优的填法都不能完成，更不用说更不好的了。
说实话3,4这两个优化挺难想的，没看大佬的题解基本想不出来，当时自己最优就拿了50来分。还得多向大佬学习。
AC代码
#include <bits/stdc++.h>
using namespace std;
int fac[50]{0};
int fac_cnt = 0;
int max_num = 0;
int min_num = 100;
int bucket[51]{0}; // 统计每个长度的个数
int n;
int sum = 0;
int current_fac;
int filled_bucket[50]{0};
int filled_bucket_cnt = 0;
bool dfs(int l, int x, int idx)
{
// l是当次剩余的长度，x是次数，idx是上次搜到的索引
if (l == 0)
{
if (x == 2) // 剩一个一定可以拼
{
return true;
}
else
{
return dfs(current_fac, x - 1, 0);
}
}
if (l < min_num) // 剩下的比最小长度还小
{
return false;
}
for (int i = idx; i < filled_bucket_cnt; i++)
{
if (bucket[filled_bucket[i]] > 0)
{
bucket[filled_bucket[i]]--;
if (dfs(l - filled_bucket[i], x, i))
{
// cout << i << '\n';
bucket[filled_bucket[i]]++;
return true;
}
else if (l == current_fac || l == filled_bucket[i])
{
bucket[filled_bucket[i]]++;
return false;
}
bucket[filled_bucket[i]]++;
}
}
return false;
}
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int ai;
cin >> ai;
max_num = max(ai, max_num);
min_num = min(ai, min_num);
sum += ai;
if (bucket[ai] == 0)
{
filled_bucket[filled_bucket_cnt++] = ai;
}
bucket[ai]++;
}
sort(filled_bucket, filled_bucket + filled_bucket_cnt, cmp);
// 对sum求因子
for (int i = max_num; i <= sum; i++)
{
if (sum % i == 0) // 整除
{
fac[fac_cnt++] = i;
}
}
for (int i = 0; i < fac_cnt - 1; i++)
{
current_fac = fac[i];
if (dfs(fac[i], sum / fac[i], 0))
{
cout << fac[i] << endl;
exit(0);
}
}
cout << sum << endl; // 前几个都不满足则是sum
return 0;
}