【题目来源】
洛谷：[P1120 CERC 1995] 小木棍 - 洛谷
【题目描述】
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 \(50\)。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
【输入】
第一行是一个整数 \(n\)，表示小木棍的个数。
第二行有 \(n\) 个整数，表示各个木棍的长度 \(a_i\)。
【输出】
输出一行一个整数表示答案。
【输入样例】
9
5 2 1 5 2 1 5 2 1
【输出样例】
6
【算法标签】
《洛谷 P1120 小木棍》 #搜索# #枚举# #剪枝# #O2优化#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 70;
int n, len, cnt, sum;
int a[N], used[N];
//当前拼接第u根原始木棍，已拼接的长度为cur
//下一段开始拼接的小木棍为start
void dfs(int u, int cur, int start)
{if (u>cnt) {cout << len; //拼好全部，立即结束exit(0);}if (cur==len) { //拼好第u根，再拼下一根dfs(u+1, 0, 1);return ;}for (int i=start; i<=n; i++) {if (used[i]||cur+a[i]>len) continue; //不合法就跳过used[i] = 1;dfs(u, cur+a[i], i+1);used[i] = 0; //拼接a[i]失败，恢复现场，再尝试a[i+1]if (cur==0) return; //cur1:拼接第1个，失败回溯if (cur+a[i]==len) return; //cnt2:拼接最后1个，失败回溯while (i<n && a[i]==a[i+1]) i++; //cnt3:跳过与a[i]等长的元素}
}
int main()
{cin >> n;for (int i=1; i<=n; i++) {cin >> a[i];sum += a[i];}sort(a+1, a+n+1, greater<int>());for (len = a[1]; ; len++) {if (sum%len) continue; //不合法就跳过cnt = sum/len;dfs(1, 0, 1); //第一次拼好即答案}return 0;
}
【运行结果】
9
5 2 1 5 2 1 5 2 1
6