Sticks
Time Limit: 1000MS Memory Limit: 10000K
Total Sub
missions: 58000 Accepted: 12785
Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5
Source
Central Europe 1995
【原题链接】
acm.pku.edu/JudgeOnline/problem?id=1011
【题意描述】
给出N根小木棒(以下称小棒)的长度Li,已知这N根小木棒原本由若干根长度相同的长木棒(以下称原棒)分解而来。要求出原棒的最小可能长度。
【数据范围】
木棒数N<=64
任意小棒长度Li<=50
【题目类型】
这题在
网络上被称为经典的深搜题,其中用到的搜索方法和剪枝技巧十分经典。就我做过这题之后的感受来看,的确如此。其中的许多技巧效果非常显著而且在其它搜索题中也经
常用到。另外建议大家在做搜索题的时候加上时间测试,以便在调
程序的时候观察和比较各项剪枝带来的效率提升。
【解题思路】
由小到大枚举所有可能的原棒长度,通过深度优先搜索尝试小棒能否组合成原棒,一旦检验成功则算法结束,当前原棒长度即为最小可能原棒长度。
枚举过程如下,设小棒的总长为SUM,最长小棒长度为MAX,从MAX开始由小到大枚举原棒长度LEN,使得LEN能被SUM整除。然后进行搜索,尝试用所有小棒拼出SUM/LEN根的原棒。
搜索过程如下,首先用一数组标USED[]记某一小棒在当前状态下是否已经被用于组合原棒,另有有两个主要参数表示搜索时的状态,CPL表示已经组合好的原棒数,RES表示当前正在组合的原棒(以下称当前原棒)已组合出的长度。在每一种状态下,尝试所有可能拼接在当前原棒上的未使用的小棒,即将满足USED=FALSE且RES+Li<=LEN的小棒接入当前原棒,传递RES的参数RES+Li,若RES+Li=LEN,传递CPL的参数CPL+1,否则,传递CPL,同时令USED=TRUE,然后进行递归,进入下一层搜索。退出下层递归后,将USED重新赋为FALSE。当CPL=SUM/LEN时,返回TRUE,表示搜索成功,一旦下一层递归返
回TRUE,当前递归也返回TRUE,不断返回,直到跳出函数调用,表示当前原棒长度为可行解,且为最小,输出。
本题的难点在于搜索的方法和剪枝的技巧。本题中用到的主要技巧有:
1. 搜索顺序。首先依据小棒长度进行由大到小的排序,在每一层
搜索时首先将长度大的小棒填入当前原棒中。因为当相对长的小棒占据了原棒的大部分空间后能大大减小可行的搜索状态。
2. 利用排序剪枝。在组合同一支原棒的时候,由于检验小棒是否可用的顺序也是由大到小的,因此在检验到一支小棒可用时,如果当前棒还合填满,可能填入当前棒的小棒的长度也不会比现在填入的这支小棒长。因此,增加一个递归参数NEXT表示可能用于组合当前棒的第一支小棒的数组下标。参数传递时,若当前正好拼成一支原棒,NEXT还原回1,否则将NEXT+1传递给下一层递归。
3. 不进行重复搜索。即在某一状态,若将某一长度的小棒填入当前原棒进行搜索无法最终拼出所有原棒,则对于当前状态,相同长度的小棒也