其中 $\text{dis}(j,i)$ 表示从 $j$ 到 $i$ 之间的距离。若设 $sum_i$ 为 $d_i$ 的前缀和，则有 $\text{dis}(j,i)=sum_i-sum_j$

最终取出 $dp_n$ 即为答案

易知该算法空间复杂度 $O(n)$，时间复杂度 $O(n^2)$

E 真值表

solution1 处理中缀表达式

以下叙述中默认大写字母 A, B, C, ... 表示一个合法的表达式，用 * 表示一个二元运算符

首先，显然连续的一段 ! 可以等价为 0 个（一共偶数个）或 1 个（一共奇数个）!，我们可以扫描一遍原表达式，得到精简 ! 之后的表达式

接着考虑建立中缀表达式树

设当前要对区间 $[l,r]$ 所表示的表达式建树，则该区间内的表达式可能有以下几种情况：

1. (...)
2. !(...)
3. A * B * C * ... * K

对于第一种和第二种情况，我们直接去掉括号和 !，然后递归地计算内层

【补充】为了确认最前的左括号和最后的右括号是匹配关系，我们可以事先用栈扫描一遍原表达式得到 $match_i$，使得若 $i$ 位置是括号，则 $match_i$ 为与其匹配的另一个括号的位置

对于第三种情况，我们找到中间这些二元运算符里最后被计算的那个，即优先级最低且位置最靠后的那个，以它为分界劈成左右两个区间递归建树

【补充】跳过合法表达式段的过程依然可以借助上文处理的 $match$ 数组完成

下图是一个建树的例子，蓝色为运算符节点，橙色为变量节点

经过上述过程，我们得到一棵表达式树，树上每个非叶子节点有一个或两个儿子

此时枚举所有变量的取值，然后后序遍历表达式树即可求出表达式的值

设表达式长度 $n$，其中变量个数为 $t$，数据组数为 $T$。则建树复杂度 $O(n^2)$，树有 $O(n)$ 个节点，计算真值表的复杂度为 $O(2^tn)$。总复杂度 $O(T(n^2 + 2^t n))$，可以通过此题

(bonus) solution2 中缀表达式转后缀表达式

观察如下两个中缀表达式与后缀表达式的对应关系

a & b | c  ->  a b & c |
a | b & c  ->  a b c & |

我们可以观察规律得出以下算法：

维护一个存放运算符的单调栈。扫描原表达式，当遇到一个变量的时候，直接将其加入到后缀表达式中；当遇到一个运算符时，查看单调栈，只要栈顶运算符优先级高于当前运算符，就不断弹出栈顶然后加入到后缀表达式中，最后将当前运算符入栈

扫描完成后，将栈内剩余的运算符依次弹出加入后缀表达式即可

当存在一元运算符时，我们令 ! 优先级最高，然后处理方式与其他二元运算符相同

! ! a | ! b & c -> a ! ! b ! c & |

当存在括号时，我们做如下处理：

• 如果扫描到一个左括号，直接将其入栈而不考虑弹出栈内其他运算符，同时将左括号的优先级设为最低，这样这个左括号就不会被其他运算符弹出
• 如果扫描到一个右括号，不断弹出栈顶加入后缀表达式，直到弹出了一个左括号为止

这样，括号就起到了 “分隔” 的作用，正确性易于理解

设表达式长度 $n$，其中变量个数为 $t$，数据组数为 $T$

综上所述，只需扫描一遍原中缀表达式即可构造对应的后缀表达式，复杂度 $O(n)$

然后枚举所有变量的取值，利用后缀表达式计算结果，复杂度 $O(2^tn)$

总复杂度 $O(2^tnT)$

【补充】该算法需要选手对后缀表达式相关内容有初步了解，故不作为题目要求复杂度