01011: Sticks
searching, http://cs101.openjudge.cn/practice/01011
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.
输入
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.
输出
The output should contains the smallest possible length of original sticks, one per line.
样例输入
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0样例输出
6
5来源
Central Europe 1995
翻译：乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。
输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。
详细解释，可以参考《算法基础与在线实践》.pdf。
基本的思路就是枚举所有可能的棍子长度。对于假定的长度，看看能否将全部木棒都用完，拼成若干根棍子。因希望棍子尽可能短，枚举棍子长度的时候，就应该从小到大枚举。这实际上也就是对搜索顺序的选择。枚举的范围则是从最长的那根木棒的长度，到木棒长度和的一半。如果都不成功，那就把所有木棒拼成一根棍子。
枚举时，不必每个长度都试，对于不是木棒长度和的因子的长度可以直接否定，无须尝试。这是本题中最容易想到，也最强的剪枝。
def dfs(unused, left, len):
if unused == 0 and left == 0:
return True
if left == 0:
left = len
for i in range(N):
if used[i] == False and length[i] <= left:
if i > 0:
if used[i - 1] == False and length[i] == length[i - 1]:
continue # 不要在同一个位置多次尝试相同长度的木棒，剪枝1
used[i] = True
if dfs(unused - 1, left - length[i], len):
return True
used[i] = False
# 不能仅仅通过替换最后一根木棒来达到目的，剪枝3
# 替换第一个根棍子是没有用的，因为就算现在不用，也总会用到这根木棍，剪枝2
# 如果我们进行尝试的时候，所使用的这根木棍长度恰好与为达到给定长度所需要的长度相等
# （也就是说使用了这根木棍就可以开始新尝试），
# 亦或此时恰好开始一次新的尝试，得到的结果是False，那么就说明这个给定长度不满足条件。
if length[i] == left or left == len:
break
return False
while True:
N = int(input())
if N == 0:
break
length = [int(x) for x in input().split()]
length.sort(reverse=True) # 排序是为了从长到短拿木棒进行尝试
totalLen = sum(length)
for L in range(length[0], totalLen//2 + 1):
if totalLen % L:
continue # 不是木棒长度和的因子的长度，直接否定
used = [False] * 65
if dfs(N, 0, L):
print(L)
break
else:
print(totalLen)https://blog.csdn.net/zab1998/article/details/96745672
首先要枚举原来木棒的长度，那么该从几开始，到几结束呢？范围为被截成木棍的最大长度~木棍的长度和/2。而且小木棍总长度一定是大木棒的倍数，单个大木棒不能比最长的小木棍短，如果sum/2已经测试过不合适，(sum/2,sum)这个区间里面的数就不必要尝试了，因为sum不可能是其的倍数。
把小木棍排个序，从大到小开始拼接，因为长木棍拼成木棒所需木棍更少，选择范围小，复杂度较低，深度也更小，也能比较快的判断出该木棒是否能被拼出（从搜索范围较小的开始搜，尽早排除不可能的情况）。也可以想一想：多个较短的小木棒，要比和他们总和等长的的较长的小木棍拼起来更灵活，所以我们先拼接长的，留下小的（也为了后边拼接更方便），若先拼小的，留下长的，可能最后拼不成，还得把前面的拆开。
第1个剪枝：如果当前木棍与前一个木棍相等，并且前一个木棍尝试拼接时没有成功，则不用再验证，直接进行下一个木棍。
第2个剪枝：当拼接长度为零时，即从0开始拼接木棒，尝试用当前这个木棍去拼接，但是尝试了所有的木棍都没有拼接成功，即可证明这个木棍无法拼成，直接return 0。
【陈子良 25物理学院】虽然原有题解已经很好了，但还是想展示一下我的史山代码。运行时间42ms，应该是超过大部分人了。
在这份代码中，dfs(m,x,d)表示对于待求的木棍长度d，当前已用掉m根木棍，且手头拼起来的木棍长度为x时，是否能拼成功。condition表示每根木棍是否已经使用，stack存储已使用的小木棍。对于拼成功的那一个d，如果你把stack打印出来，会发现它完全记录了如何拼这些木棍。每添加一根小木棍，我们要用回溯的方式处理condition和stack。
我们使用了以下剪枝：
剪枝1：对于待求的目标值d，它一定大于等于最长的木棍的长度M，且是木棍总长L的因数。我们遍历从M到L//2的所有L的因数作为d，如果全部失败就输出L。
剪枝2：当我们开始拼一根新的木棍时，使用当前未使用的木棍中最长的。因为这根木棍就算现在不用，之后也一定要用的，不如现在就用掉。
剪枝3：我们在拼一根木棍时，使用的小木棍长度应该是单调递减的。如果后面的木棍比前面的木棍长，那么我们一定检查过长木棍在前的状态了，现在还在检查，说明它是失败的。正因如此，我们需要一个stack记录我们使用的木棍长度，对于下一根木棍，要求其长度小于等于min(d-x,stack[-1])。
剪枝4：如果上一根木棍未使用过，且其长度与当前的木棍相同，那么现在这根木棍就不用检查了，因为上一根木棍已经检查过相同的状况了。
剪枝5：如果当前木棍是拼好一根长木棍所需的最后一根木棍，而之后拼木棍时失败了，可以直接返回失败。比如d=20，我们拼某根棍子使用了[10,5]，如果剩余未使用棍子中有一个[5]，那么我们会检查拼好[10,5,5]之后能否成功。如果最后返回失败，那么我们就不用再尝试诸如[10,5,4,1]之类的状态了。因为就算使用[4,1]，5也会出现在后面的棍子中，取代之前[4,1]的位置，其状态是完全相同的，而前面已说明这是失败的了。因此后续就不用检查了，直接返回失败。
import bisect
while True:
n=int(input())
if n==0:
break
sticks=list(map(int,input().split()))
sticks.sort()
L=sum(sticks)
M=sticks[-1]
for k in range(L//M,1,-1):
if L%k==0:
d=L//k # 剪枝1
condition=[False]*n
stack=[]
def dfs(m,x,d):
if m==n:
if x==0:
return True
else:
return False
if x==0:
# 剪枝2
for i in range(n-1,-1,-1):
if condition[i]==False:
condition[i]=True
stack.append(sticks[i])
if dfs(m+1,sticks[i]%d,d):
return True
condition[i]=False
stack.pop()
return False
a=bisect.bisect(sticks,min(d-x,stack[-1])) # 剪枝3
for i in range(a-1,-1,-1):
if not condition[i] and sticks[i]<=min(d-x,stack[-1]):
if i<a-1 and not condition[i+1] and sticks[i+1]==sticks[i]:
continue # 剪枝4
condition[i]=True
stack.append(sticks[i])
if dfs(m+1,(x+sticks[i])%d,d):
return True
condition[i]=False
stack.pop()
if sticks[i]==d-x: # 剪枝5
return False
return False
if dfs(0,0,d):
print(d)
break
else:
print(L)