动态规划解题思路与实例分析：最短路径与多阶段决策

本文主要讨论的是如何利用动态规划算法来解决信息学奥林匹克竞赛中的一个问题，涉及到计算单词树的对数长度lg和确定最后一行的起始单词序号cn。首先，通过`readln(f,n,m)`函数读取输入，获取单词树的节点数量n和行宽m。接下来，用一个循环读取每个单词的长度，并将这些长度存储在数组l中，其中l[0]被设置为m，作为计算对数长度的起点。 动态规划算法在这里的应用是典型的最优化问题解决策略。问题的核心是通过递推的方式计算每一对单词之间的距离（即lg[i,j]），这个距离是通过累加相邻单词长度并加1得到的。通过这样的计算，可以形成一个动态规划表，从下至上，逐步填充对数长度，直到找到满足条件的lg[i,n]不超过m的行。 算法的关键步骤包括初始化对角线元素lg[i,i]为单词长度k，然后对于其他行，通过逐个比较当前行与上一行的单词长度，更新对数值。当遍历到最后一行时，检查lg[i,n]是否大于m，如果超过，则说明无法在一行内容纳所有单词，输出"Print is impossible."并结束程序。如果最后一行的单词长度小于等于m，那么需要进一步确认是否所有单词可以在一行中排列，如果不能（即cn=1），则输出对应行号和单词数量，然后继续处理下一个情况。 整个过程体现了动态规划的分治策略，即分解问题为子问题，然后通过求解子问题的最优解来得出原问题的最优解。在数据结构上，使用二维数组h来存储每条路径的长度，这种设计使得查找和更新对数长度的操作效率较高。 这篇文章提供了一种实用的方法来解决信息学竞赛中的动态规划问题，特别是关于单词树布局的最优化问题，展示了动态规划在实际问题中的应用和计算逻辑。