动态规划解题策略：杭电ACM课件解析

"这篇资料是关于ACM竞赛中的动态规划讲解，主要分析了两个问题：动态规划求解老鼠抓猫问题以及计算直线交点数的问题。资料来自于杭电的课程，并涉及动态规划基础和实际应用。" 在动态规划中，我们通常会遇到一个问题的最优解可以通过构建子问题的最优解来获得。在这个案例中，讨论了一个关于老鼠抓猫的经典问题。问题描述如下：给定一组老鼠，每只老鼠有两个属性，重量W和速度S。我们需要找到最长的一串老鼠，使得序列中的每只老鼠都比它后面的老鼠重，并且速度慢。这是一种基于排序的动态规划问题。 首先，我们按照重量W对老鼠进行升序排序，然后按照速度S降序排列。这样，每只老鼠都是重量最大的，但速度不是最快的老鼠。 接下来定义动态规划的状态f[i]，它表示从Mice[0]到Mice[i]这一段中，最长的符合条件的老鼠序列长度。对于f[i]，我们可以遍历前面的j（1 <= j < i），如果Mice[i]的重量大于Mice[j]且速度小于Mice[j]，那么f[i]可以基于f[j]加1来扩展。初始状态设置为f[i] = 1，意味着每只老鼠至少可以单独形成一个长度为1的序列。 此外，资料还引入了一个计算直线交点数的问题。当平面内有n条直线，没有三条共点时，我们不仅要找到所有直线最多可能的交点数，还需要找出所有可能的不同交点数情况。通过列举小规模问题（如n=1,2,3）的解，可以发现动态规划的思路：对于第n条直线，我们可以考虑它与前面n-1条直线的交点情况。通过分析n=4的情况，我们归纳出公式，即m条直线的交点方案数由m-r条平行线与r条直线交叉的交点数加上r条直线之间的交点方案数构成。 这份资料提供了动态规划在解决实际问题中的应用示例，包括排序和状态转移矩阵的构建，以及如何通过归纳法解决特定问题。对于ACM竞赛的参赛者和学习动态规划的初学者来说，这些都是非常有价值的学习材料。