算法艺术与信息学竞赛中小木棍的解析

来源：百度知道 编辑：UC知道 时间：2024/06/04 10:06:10
看不懂刘汝佳的黑书-算法艺术与信息学竞赛中第181页中例题2小木棍的解析..谁能详细地解释一下...
http://acm.pku.edu.cn/JudgeOnline/problem?id=1011
题目大意：给出n根小棍的长度，拼成若干根长棍，要求这些长棍的长度相等，并且小棍刚好都用完，问能拼成的长棍的最短长度是多少?
我是想明白黑书中的解析
最好能说说黑书中的剪枝条件

很遗憾 虽然我手边书架正好有这么一本书 但是我发觉水平实在有限 帮不了你啊 反正我就晕了 连程序1 程序2在哪我都看不出来 实在抱歉呐~！
____________________________________以上是原文————
接下来 我细细地想了一下 我的思路是这样的
如果本题目不是求的最小可能长度 ，而是要求一个原长度的话 就好解决了 木棍本来就由长棍折成的 总和肯定匹配 因此 我最初的想法是直接使用2路归并算法 两两相邻的相加
最后 我发现这个思路正好相反 对照书上的意思是

先取最长的小棍 然后与最短小棍组合
将迭代传给第二长小棍 若其与剩下小棍长度之和与第一组相等 则继续迭代
若不相等则返回上一步迭代

这就是作者所说的深度优先搜索吧 这样确实能够取得最小的长棍长度
_____________________以下是对解释的补充—————————————

本来，像这种使用队列来存储的算法 怎么说都会认为是广度优先算法
地球人都知道
不过 这个题目并没有说是将每一条棍子都砍成两段，而是折成几段
这就意味着 仅仅进行上面的 两轮迭代是不够的
当第一段最长的那段从队列出来之后 也就是在两段的层次上不能匹配的时候
它会入栈 进行更多段的匹配
而只有在外面套上这么一层的迭代 才真正是深度优先算法

当然了，作者给的提示是 以最短小棍为起点 用长段来匹配 而我现在是以最长棍为起点 用短棍来匹配 是有点小小的不同 但我个人认为 过程是一样的

这个问题 真可恶 害我晚上睡不好觉 睡了下 还得爬起来

建议你 说下题目 。。。。