UP主的那根小木棍
哈喽各位亲爱的读者朋友们大家早上中午晚上好！又到了我的更新时间~今天的题目稍微有亿点点难~也请感兴趣的同学认真思考一下下。今天的音乐会稍微舒缓一点，方便大家思考。让我们点开下面的音乐，开启今天的内容吧！
今天，我们来对付小！木！棍！
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入两行，第一行是木棍的个数，第二行是每个木棍的长度
输出一个数，即最小的木棍可能长度（彻底忽略50+的木棍）
example stick.in:
9
5 2 1 5 2 1 5 2 1
example stick.out
6
如果有兴趣的话，请先进行一些思考，然后再往下翻看题解。
这种题的解决方案一般是DFS。但是如果你只进行单纯的DFS的话，那最坏的情况下计算量就会是一个相当恐怖的数字，超时也就是必然的了。所以，我们需要进行剪枝。
对于这道题而言，如果你将木棍从大到小进行排列复原小木棍，你就能保证同一根大木棍被小木棍拼成的时候拼的具体方案是唯一的。如果平均一根大木棍有4个小木棍组成的话，我们的计算量就能减少大约96%。（原来4个木棍有24种排列法）并且单根大木棍越长，减少的计算量越多。
要想实现这种效果，首先我们需要对我们收集的木棍进行排序整理。这里使用sort函数就很好。
这就够了吗？当然不是！
核心的部分还在DFS里。整体而言，我的搜索工作的关键词是“单调”——最开始的最大的小木棍长度必须是递减的，在单个大木棍里拼小木棍的时候还是从大到小递减。为了减小我们DFS的工作量，我们可以初步进行可能的长度的筛选。刚才在进行的输入中，我已经统计了木棍的总长度和最大小木棍的长度。由此我们就可以以小木棍的总长为上限，最大小木棍长为下限，将在其中间的，总长的因数（包括总长本身）作为可能的大木棍长度试图进行木棍的复原，并且从小往大搜索，一旦搜索到可行的木棍长度即可进行输出，结束程序。
DFS模块里我需要4个参数跟着我走：已经复原的木棍数量、现在的木棍拼出了多少、假设大木棍的长度和单调向下搜索的起点位置。结束搜索的状态有两种判定方式：一种是所有的木棍都已经用完，第二种是拼上的木棍总长度等于输入时统计的总长度。相比之下，我认为第二种明显方便不少。
在DFS过程中，我们应该想到几种过程中的情况：一种是拼上的木棍只剩下一点点，并且已经没有小木棍可以满足它的需求了。这个时候我们就应该结束这轮搜索——这样拼肯定是错的。还有一种是一根大木棍已经拼完，这时候我们就需要及时的将木棍清空，再进行下一轮的搜索。其中拼完的大木棍计入数据，跟着变量来到下一轮DFS函数里。
当然，更多时候我们还是需要用可能的木棍一个一个的试验。这里写一个for循环就行，但是UP还是会提醒一下一个非常重要的剪枝技巧——第一个木棍记得千万不要换，就用当前能用的最大的木棍。最后一个木棍如果能完美填满这个大木棍的话也不要再动了——毕竟对于这个题来说，也许用更短的木棍也能达到和上面同样的效果，但是更短的木棍凭借着他的灵活性，会有更多的用处，不是吗？（虽然这种设定并不会节约很多时间）
具体的代码如下（考虑到B站的代码块还是很不成熟，我在此先放上一个我写的CSDN题解的备用链接：https://blog.csdn.net/weixin_45523749/article/details/112119255）
总体而言，这道题中可以减少计算量的地方有很多。而其中最重要的一点就是：从大到小，排好序列有序搜索。这样就可以真正意义上做到搜索不重复了。
好啦，今天UP的文章就到这里啦！喜欢和话记得，一 键 三 连 哦！各位拜拜~~~
