AcWing 167. 木棒
【题目描述】
乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过$50$个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序,帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
【输入格式】
输入包含多组数据,每组数据包括两行。
第一行是一个不超过$64$的整数,表示砍断之后共有多少节木棍。
第二行是截断以后,所得到的各节木棍的长度。
在最后一组数据之后,是一个零。
【输出格式】
为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。
【数据范围】
数据保证每一节木棍的长度均不大于$50$。
【输入样例】
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
【输出样例】
6
5
【分析】
直接上剪枝思路:
- 可行性剪枝:木棒长度$length$必须能整除木棍总长度$sum$
- 优化搜索顺序:将木棍长度从大到小排序,优先枚举长度较大的,这样搜索分支较少
- 排除等效冗余:
(1)按照组合数方式枚举,因为一根木棒如果由$1,2,3$号木棍拼接而成,那么$2,1,3$等其它组合方式也同样能拼成;
(2)如果当前木棍拼到当前木棒里失败了,那么跳过所有与之等长的木棍,因为换任何一根等长的木棍效果也是一样的;
(3)如果当前木棍$i$拼到当前木棒的第一个位置失败了,那么整个方案失败。可以使用反证法,如果最后方案能成功,那么木棍$i$一定在后面的某根木棒$j$中,由于顺序不影响结果,可以将木棍$i$放到木棒$j$的第一个位置,然后将木棒$j$与之前$i$作为开头的那根木棒进行交换,则得到$i$作为第一根木棍的合法方案,产生矛盾;
(4)如果当前木棍$i$拼到当前木棒的最后一个位置且将当前木棒成功拼完,而拼之后的木棒失败了,那么整个方案失败。同样使用反证法,如果最后方案能成功,那么之前那根木棒会使用其它的几根木棍比如$j,k$,这几根木棍一定也得填满这根木棒的末尾,也就是长度之和等于$i$的长度,然后$i$会在之后的某根木棒中,那么可以交换$i$和$j,k$,这样整个方案也是成功的,而且$i$在之前那根木棒的最后一个位置,产生矛盾。
【代码】
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 70;
int w[N];
int sum, length;//sum表示木棍总长度,length表示当前枚举的木棒长度
bool st[N];
int n;
//当前已经拼好u根木棒,当前木棒长度为s,需要从第start根木棍开始选
bool dfs(int u, int s, int start)
{
if (u * length == sum) return true;
if (s == length) return dfs(u + 1, 0, 0);
for (int i = start; i < n; i++)
{
if (st[i] || s + w[i] > length) continue;//已经用过或者拼上后长度过长则剪枝
st[i] = true;
if (dfs(u, s + w[i], i + 1)) return true;
st[i] = false;
//如果当前木棍放在木棒的第一根或最后一根(当前木棒已拼完)失败了,那么整个方案就失败了
if (s == 0 || s + w[i] == length) return false;
//如果当前木棍失败了,那么用与之等长的木棍也一定会失败,因此跳过等长的木棍
while (i + 1 < n && w[i + 1] == w[i]) i++;
}
return false;
}
int main()
{
while (cin >> n, n)
{
memset(st, false, sizeof st);
sum = 0;
for (int i = 0; i < n; i++) { cin >> w[i]; sum += w[i]; }
sort(w, w + n, greater<int>());
for (length = 1; length <= sum; length++)
if (sum % length == 0 && dfs(0, 0, 0))//木棒长度必须能被总长度整除
{
cout << length << endl;
break;
}
}
return 0;
}