题目描述
乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序,帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式:
输入包含多组数据,每组数据包括两行。
第一行是一个不超过 64 的整数,表示砍断之后共有多少节木棍。
第二行是截断以后,所得到的各节木棍的长度。
在最后一组数据之后,是一个零。
输出格式:
为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。
样例:
输入样例:
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例:
6
5
算法:
DFS搜索与剪枝:
我们假定是说木棒是拼接之前散落的木头,木棍是之前拿来的等长的完整的木头
----------
_**千万注意我们要求的是所有木棒都被选上,不能不选当前某个长度的木棒!!!!!!!!!!!!!!!!**_
----------
我们现在要做的是将这些散落的木棒拼成等长的一组木棍:
举个例子来看:
9
5 2 1 5 2 1 5 2 1
将所有长度是5的木棒和2的木棒拼接起来,那么会组成三个长度是6的木棍,再把剩下的长度是2的木棒拼接在一起构成一个新的6的木棍
最小长度就是6
我们可以从1开始枚举所有可能的长度,逐渐递增,那么第一个满足条件的长度就是最小的长度
很显然我们所有木棒的长度之和sum肯定能整除这个最小长度
除此之外,我们按照拼凑木棍的去爆搜,也就是说按枚举所有木棒按照那个最小长度去拼接木棍(够了长度就去拼新的木棍)
当我们枚举完所有木棒时,木棍也正好全部拼接完毕(等长且完整),那么这就是一个合法的方案
//此时我们在dfs时就要传进去两个参数:当前的木棒数u(从1开始),当前的木棒的长度len
//此时我们在思考所有的剪枝:
1.从枚举顺序出发:
我们可见,每次拼接成木棍时都可能会有多个木棒来拼凑,我们尽可能的让更少的木棒去拼凑完整的木棍
那么只需要按照木棒的长度从大到小枚举所有木棒来拼凑即可,因外当要拼凑出的木棍长度固定时,我们选的木棒长度越长
那么这根木棍剩下的要拼凑的长度就越短,那么剩下选择的木棒数就越少,那么就可以减少可供选择的木棒的数量
----------
2.从冗余性剪枝出发
我们在枚举木棒时,假设木棒是由编号为 3 6 7 0的木棒拼接而成的
我们按照 3 6 7 0号拼接木棍和按照 7 6 0 3的顺序去拼接效果是一样的,比如3是最长的,枚举3时会枚举完剩下的3个编号,组成3 6 7 0拼成的木棍
那么我们枚举到中间的长度假设说是7号时,他也还会枚举到剩下的3个编号组成7 6 0 3的木棍
那么就会有冗余重复的拼接方案
我们可以人为规定一个拼接的顺序,按照编号从小到大的顺序去拼接
----------
3.从可行性剪枝出发:
//这比较难理解:先说明结论:假设我们枚举的木棍是i,将其放到假设说木棍1的第二个位置失败了,那么与木棒i等长的所有木棒都不能再放到这个位置,否则都会失败
//也就是说当我们在拼接某个木棍的某个位置时,我们当前枚举的木棒不能放到这个位置,那么与当前我们枚举的木棒长度相等的所有木棒都不能放在这个位置上
先说明一下这里的失败到指的是什么失败?
这里指的是在第一个木棍的第二个位置放上木棒i的话可能会导致全方案的失败,什么意思?这里看图会比较详细
木棒i
1.****-----****
2.************* 也就是说在这个位置放上木棒i的话,这根木棍可能没问题,但很可能导致后续方案的失败(比如木棍4拼不成)
3.************* 那么这里就不能放所有与木棒i长度相同的其他木棒
4.****** 失败了 这里有可能会有人犟嘴:那么我这里放这个木棒会导致后续的失败,那么是不是有可能是这个木棒放到别处合适,
但是和他相同长度的其他木棒放这也行呢?这里我们采用反证法证明
//我们假设木棒i+1和木棒i是等长的,那么假设当前的这个位置,假设还是的第一个木棍的第二个位置不行
//****-----****
// i ----------->整个方案失败
那么假设不能放i木棍但是可以放与之等长的i+1个木棍,我们前提中明说,所有木棒都要被用上,那么i木棒不放在这里那么一定被放在了其他木棍上
假设他去拼第二根木棍了:与之等长度的i+1木棒代替它放在了这里,并且假设这样换之后这种方案不会导致最终拼不成所有的木棍
1.****-----*****
i+1
2.-----*********
// i
3.**************
4.************** 成功了?不可能!
那么这种方案真的可以成功吗?当然是不可能的,既然你i和i+1木棒等长,那么我让i和i+1木棒换换位置
i+1去代替i在第二个木棍的位置,i去代替i+1在第一个木棍的位置,那么交换后不会影响任何地方(毕竟是等长的)
神奇的是i又换到了第一个木棍的第二个位置上,但是我们说了这样会导致失败,而两种方案又是等价的
因此这个位置就不能放所有与之等长的木棒
这里在注意一下:当出现剪枝3的情况时,只是说明当前这个位置上不能放长度是i的木棒,换其他长度的来放即可
_**并不是再说当前这种方案就是根本性错误的,不是怎么放都会导致失败,这里和剪枝4,5有本质上区别
**_
----------
///剪枝4:当我们在拼接某一根木棍时,开头要放的木棒就会导致整个方案的失败,那么就会导致这个方案本身就不行(本质上就不行,直接下一个长度)
//比如说:第二个木棍的开头枚举的木棒就会导致失败
1.************
2.-----*******
i ------------>整个方案就不行,重新枚举下一个最小的长度
3.************
4.**** 失败了
//那么又有的懵了,你刚才那个剪枝3不是跳过这个长度的木棒就行了吗,那你这个剪枝4怎么连换长度的机会都没了?
//听我说,还是反证法来说:
//假设这个方案是可以成功的,那么我们不在这个木棍的开头放这个木棒了,换成别的木棒,由于我们说了要用上所有的木棒
//那么这个木棒i不能放在这里当开头,那么一定会放在其他木棍的其他位置:假设如图:
1.*************
2.---**********
代替i的另一个木棒j
3.****-----****
i
4.************* 成功了?不可能!
//还是和上面的剪枝3一样,我们将i换到木棍3的开头:也不会影响其他的任何因素
//2.---**********
//3.-----********
欸!你这个木棒i不能当木棍2的开头,当然也不能当木棍3的开头了,不然你这个i再和木棍2开头换一下,那不就又成了可以放在2开头了吗?
这根本上不可能,因此无论你怎么放这个木棒i,都会导致整个方案的失败,因此一旦出现某个木棍的开头就出问题时,整个方案都会出现问题,就失败
剪枝5:与4差不多,木棍的结尾出问题时,整个方案失败
参考文献:
y总提高课
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=64;
int n,sum,lenth;//n记录总木棒数,sum记录长度总和,lenth记录最长的木棒的长度
int sticks[N];
bool st[N];
bool dfs(int u,int cur,int start)//剪枝2,内部顺序化搜索
{
if(u*lenth==sum) return true;//枚举完所有长度刚刚好就是一种完美的方案了
///拼完当前的木棍,接着拼下一个木棍
if(cur==lenth) return dfs(u+1,0,0);
for(int i=start;i<n;i++)
{
if(st[i]) continue;
int l=sticks[i];
if(cur+l>lenth) continue;
st[i]=true;
if(dfs(u,cur+l,i+1)) return true;
st[i]=false;
///以上还没有返回true的说明当前木棒失败,进行剪枝
///剪枝4:
if(!cur)///在开头失败,说明整个方案失败
return false;
///剪枝5:
if(cur+l==lenth) return false;
///剪枝3:
int j=i;
while(j<n && sticks[j]==l) j++;//跳过相同的
i=j-1;
}
return false;
}
int main()
{
while(cin>>n,n)
{
sum=0,lenth=0;
for(int i=0;i<n;i++)
{
int l; cin>>l;
sticks[i]=l;
if(l>50) continue;
sum+=l;
lenth=max(lenth,l);
}
///从大到小枚举所有木棒,剪枝1
sort(sticks,sticks+n);
reverse(sticks,sticks+n);
memset(st,0,sizeof st);
for(int i=0;i<n;i++)
if(sticks[i] > 50)
st[i]=true;
///最短长度从最长的木棒的长度开始往上枚举可能的最小长度:
while(lenth)
{
if( sum%lenth==0 && dfs(0,0,0) )//dfs:1是木棍编号,2是当前木棍的长度,3是木棍内部木棒的编号(人为限定从小到大开始)
{
cout<<lenth<<endl;
break;
}
lenth++;
}
}
return 0;
}