道路重建：动态规划解决农场子树分离问题

道路重建（Problem 1947）是ACM算法竞赛中一道涉及动态规划的经典题目，出自《算法艺术与信息学竞赛》。该题目背景设定在农夫John的农场，农场上一共有n个牛舍，形成一棵树状结构，其中每个牛舍间仅有一条双向道路相连。由于地震可能导致农场的连通性破裂，John想知道为了使至少p个牛舍形成一个独立的子树（不与其他部分相连），他需要破坏哪些道路。 题目关键点在于设计一个动态规划策略来解决。动态规划在这里主要用于求解最小操作数，即需要最少毁坏的道路数量。设d[i, j]表示从第i个到第j个牛舍所需的最少括号添加量（这里用括号作为抽象模型，实际上代表道路的破坏），状态转移函数需要考虑四种情况： 1. 当子串S的结构是(S')或者[S']（两个连续的闭合括号）时，由于这些已经构成了一个完整的子序列，所以d[i+1, j-1]即为所需的最小括号数。 2. 如果S由两个独立的部分S'和[S']组成，那么添加一个括号将它们合并为一个规则序列，所以d[i+1, j] + 1。 3. 当S的结构是S'或者S'（一个开括号和另一个部分）时，我们需要在第一个部分后面添加一个闭合括号，使得d[i, j-1] + 1。 4. 对于长度大于1的子串，意味着需要分别计算左右两部分的最小括号数，然后相加，即d[i, k] + d[k, j]。 解题时，从每个节点出发，递归地更新d数组，直到遍历整个树形结构，找到破坏最少道路的组合。这个过程利用了动态规划的效率优化，避免了重复计算，对于大型农场（n≤150）来说，能够有效地找到最小的破坏路径。 这道题目不仅锻炼了对动态规划的理解，还涉及到递归和搜索算法的运用，以及如何合理地定义状态和状态转移，是算法竞赛中提升解决问题能力的好题目。