区间动态规划例题：布尔括号化问题（带权值版本） 题目描述 给定一个布尔表达式，由符号 T （真）、 F （假）、 & （与）、 | （或）、 ^ （异或）以及 ( 、 ) 组成。表达式中还可能包含整数权值，这些权值附加在操作符上。我们的目标是通过不同的括号化方式，计算整个表达式为真（ T ）时所能得到的最大权值和。 具体来说，每个操作符 & 、 | 、 ^ 都有一个关联的权值。当我们对表达式进行括号化时，每使用一个操作符进行运算，我们就可以获得该操作符的权值。最终目标是使得整个表达式的结果为 T ，并且在所有能得到 T 的括号化方式中，找到权值累加和最大的那个。 例如，表达式： T | F ^ T ，操作符权值分别为： | -> 3， ^ -> 5。 一种括号化方式： (T | F) ^ T ，结果为 (T | F) = T ，然后 T ^ T = F ，结果为 F ，无效。 另一种括号化方式： T | (F ^ T) ，结果为 F ^ T = T ，然后 T | T = T ，结果为 T ，总权值为 3 + 5 = 8。 这个表达式的最大权值和就是 8。 解题过程 我们将使用区间动态规划来解决这个问题。核心思想是定义一个DP数组，用于存储区间内表达式得到某个结果（真或假）时的最大权值。 定义状态 我们定义 dp[i][j][0] 为在子表达式 s[i:j+1] 范围内，通过不同的括号化方式，表达式结果为 F 时能获得的最大权值和。 定义 dp[i][j][1] 为在同样的子表达式范围内，表达式结果为 T 时能获得的最大权值和。 这里 i 和 j 是子表达式的起始和结束索引（包含）。 状态转移方程 考虑子表达式 s[i:j+1] ，我们尝试在每一个操作符 op_k （位于索引 k ，且 i < k < j ，并且 s[k] 是一个操作符）处进行分割。 将表达式分割为左右两部分： s[i:k] 和 s[k+1:j+1] 。 根据操作符 op_k 的类型，以及左右两部分可能的结果（真或假），来计算当前区间 [i, j] 得到真或假时的最大权值。 对于每个操作符 op_k ，其权值为 val_k ，状态转移如下： 如果 op_k 是 '&' （与）： 结果为真：左右都必须为真。 dp[i][j][1] = max(dp[i][j][1], dp[i][k-1][1] + dp[k+1][j][1] + val_k) 结果为假：左真右假、左假右真、左假右假。 dp[i][j][0] = max(dp[i][j][0], dp[i][k-1][1] + dp[k+1][j][0] + val_k, dp[i][k-1][0] + dp[k+1][j][1] + val_k, dp[i][k-1][0] + dp[k+1][j][0] + val_k) 如果 op_k 是 '|' （或）： 结果为真：左真右真、左真右假、左假右真。 dp[i][j][1] = max(dp[i][j][1], dp[i][k-1][1] + dp[k+1][j][1] + val_k, dp[i][k-1][1] + dp[k+1][j][0] + val_k, dp[i][k-1][0] + dp[k+1][j][1] + val_k) 结果为假：左右都必须为假。 dp[i][j][0] = max(dp[i][j][0], dp[i][k-1][0] + dp[k+1][j][0] + val_k) 如果 op_k 是 '^' （异或）： 结果为真：左真右假、左假右真。 dp[i][j][1] = max(dp[i][j][1], dp[i][k-1][1] + dp[k+1][j][0] + val_k, dp[i][k-1][0] + dp[k+1][j][1] + val_k) 结果为假：左真右真、左假右假。 dp[i][j][0] = max(dp[i][j][0], dp[i][k-1][1] + dp[k+1][j][1] + val_k, dp[i][k-1][0] + dp[k+1][j][0] + val_k) 初始化 对于长度为1的子表达式（即单个字符）： 如果 s[i] 是 'T' ，则 dp[i][i][1] = 0 （因为单个 T 本身就是真，但尚未使用任何操作符，权值为0）， dp[i][i][0] = -inf （或者一个非常小的数，表示不可能，因为单个 T 不可能为假）。 如果 s[i] 是 'F' ，则 dp[i][i][0] = 0 ， dp[i][i][1] = -inf 。 计算顺序 我们按照子表达式的长度 len 从小到大进行遍历。 对于每个长度 len ，遍历所有可能的起始位置 i ，并计算结束位置 j = i + len - 1 。 对于每个区间 [i, j] ，遍历所有可能的分割点 k （ k 从 i+1 到 j-1 ，步长为2，因为操作符和操作数是交替出现的，例如 T | F ，索引1是操作符）。 最终结果 整个表达式 s[0:n-1] （ n 为表达式长度）为真时的最大权值和就是 dp[0][n-1][1] 。 示例推导 以表达式 "T|F^T" 为例，操作符权值： | -> 3, ^ -> 5。 初始化 （长度为1的子表达式）： dp[0][0][1] = 0 (T), dp[0][0][0] = -inf dp[1][1][0] = 0 (F), dp[1][1][1] = -inf dp[2][2][1] = 0 (T), dp[2][2][0] = -inf 长度为3的子表达式 ： 区间 [0, 2] ("T|F")，操作符在索引1 ( | , 权值3)： 结果为真： (T|F) -> max( dp[0][0][1] + dp[2][2][1] + 3, dp[0][0][1] + dp[2][2][0] + 3, dp[0][0][0] + dp[2][2][1] + 3 ) -> max(0+0+3, 0+(-inf)+3, (-inf)+0+3) -> max(3, -inf, -inf) = 3 dp[0][2][1] = 3 结果为假： (T|F) -> dp[0][0][0] + dp[2][2][0] + 3 -> (-inf) + (-inf) + 3 = -inf dp[0][2][0] = -inf 区间 [1, 3] ("F^T")，操作符在索引2 ( ^ , 权值5)： 结果为真： (F^T) -> max( dp[1][1][1] + dp[3][3][0] + 5, dp[1][1][0] + dp[3][3][1] + 5 ) -> max( (-inf)+(-inf)+5, 0+0+5 ) -> max(-inf, 5) = 5 dp[1][3][1] = 5 结果为假： (F^T) -> max( dp[1][1][1] + dp[3][3][1] + 5, dp[1][1][0] + dp[3][3][0] + 5 ) -> max( (-inf)+0+5, 0+(-inf)+5 ) -> max(-inf, -inf) = -inf dp[1][3][0] = -inf 整个表达式 （长度为5，区间 [0, 4] ，即 "T|F^T" ）： 我们遍历所有操作符作为最后运算的分割点。 分割点1 ( | , 权值3)：左 [0,0]="T" ，右 [2,4]="F^T" 结果为真： (T | (F^T)) -> max( dp[0][0][1] + dp[2][4][1] + 3, dp[0][0][1] + dp[2][4][0] + 3, dp[0][0][0] + dp[2][4][1] + 3 ) -> max(0 + 5 + 3, 0 + (-inf) + 3, (-inf) + 5 + 3) -> max(8, -inf, -inf) = 8 所以通过分割点1，我们得到 dp[0][4][1] 至少为 8。 分割点3 ( ^ , 权值5)：左 [0,2]="T|F" ，右 [4,4]="T" 结果为真： ((T|F) ^ T) -> max( dp[0][2][1] + dp[4][4][0] + 5, dp[0][2][0] + dp[4][4][1] + 5 ) -> max(3 + (-inf) + 5, (-inf) + 0 + 5) -> max(-inf, -inf) = -inf (无效) 所以分割点3不能得到真。 因此，整个表达式的最大权值和为 dp[0][4][1] = 8 。 这个结果与手动计算一致。通过这个动态规划过程，我们可以系统地计算出任意布尔表达式在结果为真时的最大权值和。