布尔括号化问题（带权值版本）

题目描述：
给定一个布尔表达式字符串，由字符 'T'（真）、'F'（假）以及运算符 '&'（与）、'|'（或）、'^'（异或）组成。表达式中的每个布尔值都有一个对应的权值。我们的目标是通过添加括号来改变运算顺序，使得整个表达式的值为真（T）时，所有为真的子表达式权值之和最大。

解题过程：

1. 问题分析：

• 输入是一个交替的布尔值和运算符的序列，如：T & F | T ^ F
• 每个布尔值有一个正整数的权值
• 我们需要找到所有可能的括号化方式中，使得最终结果为真时，所有为真的子表达式的权值之和最大

2. 状态定义：
   定义两个DP数组：

• dp_true[i][j]：表示子串 s[i...j] 通过括号化能得到真的最大权值和
• dp_false[i][j]：表示子串 s[i...j] 通过括号化能得到假的最大权值和

3. 状态初始化：
   对于长度为1的子串（即单个字符）：

• 如果 s[i] == 'T'：
  • dp_true[i][i] = weight[i]（权值）
  • dp_false[i][i] = 0
• 如果 s[i] == 'F'：
  • dp_true[i][i] = 0
  • dp_false[i][i] = weight[i]（权值）

4. 状态转移：
   对于每个区间 [i, j]，我们枚举所有可能的分割点 k（在运算符位置分割）：

• 当运算符是 '&'（与）时：

  • 结果为真：左右都为真
    true_val = dp_true[i][k-1] + dp_true[k+1][j] + weight[k]
  • 结果为假：左真右假 或 左假右真 或 左假右假
    false_val = max(dp_true[i][k-1] + dp_false[k+1][j], dp_false[i][k-1] + dp_true[k+1][j], dp_false[i][k-1] + dp_false[k+1][j]) + weight[k]

• 当运算符是 '|'（或）时：

  • 结果为真：左真右真 或 左真右假 或 左假右真
    true_val = max(dp_true[i][k-1] + dp_true[k+1][j], dp_true[i][k-1] + dp_false[k+1][j], dp_false[i][k-1] + dp_true[k+1][j]) + weight[k]
  • 结果为假：左右都为假
    false_val = dp_false[i][k-1] + dp_false[k+1][j] + weight[k]

• 当运算符是 '^'（异或）时：

  • 结果为真：左真右假 或 左假右真
    true_val = max(dp_true[i][k-1] + dp_false[k+1][j], dp_false[i][k-1] + dp_true[k+1][j]) + weight[k]
  • 结果为假：左真右真 或 左假右假
    false_val = max(dp_true[i][k-1] + dp_true[k+1][j], dp_false[i][k-1] + dp_false[k+1][j]) + weight[k]

5. 最终结果：
   整个表达式为真时的最大权值和就是 dp_true[0][n-1]，其中 n 是字符串长度。

6. 实现细节：

• 按区间长度从小到大计算
• 注意运算符位置和操作数的对应关系
• 时间复杂度：O(n³)，空间复杂度：O(n²)

这个算法通过动态规划系统地考虑了所有可能的括号化方式，同时考虑了每个子表达式的权值，确保找到权值和最大的方案。