题面

现有一个由左括号 ‘(’ 和右括号 ‘)’ 两种共 $n$ 个字符组成的字符串，每个括号都有一个权值 $v_i$ 。每次操作可以交换第 $k$ 和第 $k + 1$ 个括号，当且仅当第 $k$ 个括号为左括号 ‘(’ 同时第 $k + 1$ 个括号为右括号 ‘)’。刚开始时分数为 $0$ ，每次操作可获得分数 $v_k \times v_{k + 1}$ 。

试问经过任意次操作后可以得到的最大总分。

数据范围： $1 \le n \le 10^3$

$-10^3 \le v_i \le 10^3$

题目链接

分析

动态规划

首先我们不难发现交换具有以下特性：

每一个左括号只可能往右走，因此不论如何变换，最初在第 $i$ 个左括号左边的右括号将永远在其左边；
假设初始时第 $i$ 个左括号在第 $j$ 个左括号的左边，那么不论如何变换第 $i$ 个左括号将永远在第 $j$ 个左括号左边。这对右括号也成立。换句话说，左括号之间的相对位置不会发生改变，同时右括号之间的相对位置也不会发生改变。

也就是说，唯一变化的也就是左括号与右括号之间的相对位置。基于此，我们不妨用状态 $dp[i][j]$ 来描述第 $i$ 个左括号在第 $j$ 个右括号右边（且在第 $j + 1$ 个右括号左边）时我们可得到的最大得分。既然第 $i$ 个左括号在第 $j$ 个右括号右边意味着第 $i + 1$ 以及以后的左括号都必然在第 $j$ 个右括号右边，那么 $dp[i][j]$ 显然可以由 $dp[i][k] \ (j \le k \le \text{rightNum})$ 转移而来（其中 $\text{rightNum}$ 代表右括号的个数）：只需要再其基础上加上把第 $i$ 个左括号移动到第 $j$ 个右括号右边所得的分数 $score$ 就行了。于是我们不难得到状态转移方程：

$dp[i][j] = \max{ \{ dp[i + 1][k] + score \} }$

其中：

$\text{leftRightId}[i] \le j \le \text{rightNum}, \ j \le k \le \text{rightNum}$

需要说明的是， $\text{leftRightId}[i]$ 代表第 $i$ 个左括号左边的与其最临近的右括号。显然，第 $i$ 个左括号不可能被交换到它最早所在位置的左边去（即第 $\text{leftRightId}[i]$ 个右括号之前的右括号右边）。

接下来要解决的问题是 $score$ 如何计算。

我们注意到如果能将第 $i$ 个左括号移动到第 $j$ 个右括号右边，那么第 $i$ 个左括号和第 $j$ 个右括号之间必然全都是右括号。显然，如果我们要将第 $i$ 个左括号移动到第 $j$ 个右括号右边，在此过程中必然需要先与其间的右括号发生移动。我们记第 $i$ 个左括号与第 $j$ 个右括号之间（包含第 $j$ 个右括号）的所有右括号权值之和为 $sum$ ，那么这个过程所获得的分数显然为（其中 $\text{leftVal}[i]$ 指第 $i$ 个左括号的权值）：

$score = \text{leftVal}[i] \times sum$

至于 $sum$ 如何计算，我们联想到第一条性质：第 $i$ 个左括号左边的右括号将永远在其左边。因此我们可以预处理右括号权值的前缀和 $\text{rightSum}$ 。由此，第 $i$ 个左括号和第 $j$ 个右括号这个区间中的右括号也就等效于第 $\text{leftRightId}[i]$ 个右括号（不包含）和第 $j$ 个右括号之间的右括号。故 $sum$ 可表示为：

$sum = \text{rightSum}[j] - \text{rightSum}[\ \text{leftRightId}[i] \ ]$

至此基本的转移方程式我们已经写出来了，接下来我们考虑边界。

首先， $dp[i][j]$ 应当全部初始化为 $-\infty$ ，因为其中存在不合法的状态。于此同时，当 $i$ 为最右边的左括号时显然 $dp[i + 1][k]$ 是不存在的，应取值为 $0$ ，所以在初始化的时候可以顺便将 $dp[\text{\text{leftNum}} + 1][k]$ 全部初始化为 $0$ 。

如果第 $i$ 个左括号左边不存在右括号，我们可以记 $\text{leftRightId}[i]$ 为 $0$ 。因此， $dp[i][0]$ 实际上也是需要初始化的。

最后的答案也就是 $dp[i][j]$ 中的最大值（严格地来说，应该是 $dp[1][j]$ 中的最大值）。

该算法的复杂度级别为 $\mathcal{O}(N^3)$ 。

优化

我们注意到在上述实现中每次转移时都需要在 $dp[i + 1][k]$ 中寻找最大值。于是我们思考，如果我们直接将状态 $dp[i][j]$ 定义为第 $i$ 个左括号在第 $j$ 个右括号右边（不论是否在第 $j + 1$ 个右括号左边）时我们可得到的最大得分，那么这一层循环就可以省去了。由此我们可以写出状态转移方程：

$dp[i][j] = \begin{cases} \max{ \{ dp[i + 1][j] + score, dp[i][j + 1] \} } & \text{leftRightId}[i] \le j \le \text{rightNum} \\ dp[i + 1][j] & \text{leftRightId}[i - 1] \le j \le \text{leftRightId}[i] - 1 \\ \end{cases}$

其中， $dp[i + 1][j] + score$ 代表将第 $i$ 个左括号恰好移到第 $j$ 个右括号右边（且在第 $j + 1$ 个右括号左边）后的最大得分，而 $dp[i][j + 1]$ 则指第 $i$ 个左括号在第 $j + 1$ 个右括号右边时的最大得分。二者中的最大值也就代表了第 $i$ 个左括号在第 $j$ 个右括号右边时的最大得分。而当 $ j [i] - 1$ 时我们是无法将第 $i$ 个左括号恰好移动到第 $j$ 个括号右边（且在第 $j + 1$ 个右括号左边）的，因此此时 $dp[i][j] = dp[i + 1][j]$ 。至于 $j < \text{leftRightId[i - 1]}$ 的情况，我们在推导 $dp[i - 1]$ 的时候是用不到的，所以也不必计算。

至于 $score$ 的计算方法和预处理时的注意事项与上基本一致，就不作重复。唯一与上面不同的是， $dp[i][j]$ 中这下子不存在不合法的状态了，所以可以方便地直接初始化 $dp[i][j]$ 全部为 $0$ 。

优化后的复杂度级别为 $\mathcal{O}(N^2)$ 。

另一种转移方程

网络上的其它题解也提供了另一种与上文差别不大的转移方程的思路（参考【ZOJ-4027】 Sequence Swapping(2018浙江省赛-D题））。

$dp[i][j]$ 定义为第 $i$ 个左括号在第 $j$ 个位置及其右边时我们可得到的最大得分，我们可得到如下转移方程式：

$dp[i][j] = \begin{cases} dp[i + 1][j + 1] + score & j = len - (\text{leftNum} - i) \\ \max{ \{ dp[i + 1][j + 1] + score, dp[i + 1][j] \} } & \text{leftPos}[i] \le j \le len - (\text{leftNum} - i) - 1 \\ dp[i][j + 1] & \text{leftPos}[i - 1] \le j \le \text{leftPos}[i] - 1 \\ \end{cases}$

其中， $len$ 代表字符串的长度， $\text{leftNum}$ 代表左括号的个数。因此， $\text{leftNum} - i$ 代表当前已经排号位置的左括号个数。对于已经排号的左括号我们自然不应再去更改它的位置，因此 $j \le len - (\text{leftNum} - i)$ 。另外 $\text{leftPos}[i]$ 代表第 $i$ 个左括号的实际位置。

简而言之，第 $i$ 个左括号在第 $j$ 个位置及其右边也就意味着第 $i + 1$ 及以后的左括号都应在第 $j + 1$ 个位置及其右边。由此，该转移方程也不难理解了。

这种算法的复杂度级别也为 $\mathcal{O}(N^2)$ 。