问题2126--小木棍

2126: 小木棍

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交

题目描述

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

输入

第一行为一个单独的整数N表示砍过以后的小木棍的总数,其中N≤60,第二行为N个用空个隔开的正整数,表示N根小木棍的长度。

输出

仅一行,表示要求的原始木棍的最小可能长度

样例输入 Copy

9  
5 2 1 5 2 1 5 2 1

样例输出 Copy

6

提示

剪枝与优化

  1. 枚举原始大木棍的可能长度len,len一定在[所有小木棍最大长度,所有小木棍总长度]的范围内,该长度一定是所有小木棍和sum的因子

  2. 优化搜索顺序:从大到小枚举,减少搜索空间

  3. 排除等效冗余:1 2 3, 1 3 2是同一个方案,因此按组合的方式而非按排列的方式枚举。对于每根大木棍的片段的枚举,每个片段编号的枚举,从上一个片段编号idx+1开始枚举,也就是按照长度降序枚举

  4. 排除等效冗余:如果某小木棍用来拼凑某个长度的木棍失败了,那么使用长度相等的木棍来拼凑某个长度的木棍也会失败

  5. 如果某小木棍作为某大木棍的第一个小木棍拼接失败了,那么该方案一定失败

  6. 如果小木棍作为某大木棍的最后一个小木棍拼接成功,但是接下来递归失败了那么该方案一定失败

来源/分类

深搜