智乃的括号匹配
题目描述
智乃现在有一个仅由 "(" 和 ")" 组成长度大小为 $N$ 的字符串，字符串的每一个位置的字符都有自己的权值 $v_i$ 和代价 $c_i$。
智乃定义一对在该字符串中配对的括号对，假设左括号的坐标为 $i$，右括号为 $j$，该括号对的价值为两个括号权值的乘积 $v_i \cdot v_j$。
"配对的括号"指从右往左开始对于每一个 '('，从它开始向右找到第一个未配对的 ')' 组成一对配对的括号。例如在 "(())" 中，假设下标分别为 $1,2,3,4$ 首先找到 $2$ 位置的 '(' 与 $3$ 的 ')' 进行配对，接下来 $1$ 位置的 '(' 由于 $3$ 已经配对，所以最终 $1$ 和 $4$ 配对。
智乃定义整个字符串的价值为所有配对的括号对价值之和，注意并不要求整个字符串都是配对的。
现在对于任意下标为 $i$ 的括号，智乃可以消耗它的代价 $c_i$ 将其翻转，即 "(" 变为 ")"，")" 变为 "("。
假设智乃的最总得分为经过若干次操作后，字符串的价值减去操作的代价之和，求智乃的最大得分。
注意当字符串价值小于操作的代价和时，智乃的得分可能是负数。
输入描述:
第一行输入一个正整数 $N(1 \leq N \leq 500)$ 表示字符串的大小。
接下来输入一个长度大小为 $N$ 的字符串 $S(S_i \in \{\mathrm{'}(\mathrm{'}, \, \mathrm{'})\mathrm{'} \})$。
接下来输入 $N$ 个正整数 $v_i(−10^6 \leq v_i \leq 10^6)$ 表示字符串每个字符的权值。
接下来输入 $N$ 个正整数 $c_i(1 \leq c_i \leq 10^9)$ 表示字符串每个字符的代价。
输出描述:
仅一行一个整数，表示最大得分。
示例1
输入
2
)(
4 3
10 10输出
0说明
如果将两个括号都翻转，则代价为 20，收益为 12，这样倒亏 8，不如什么都不做。
示例2
输入
2
((
4 3
10 10输出
2说明
翻转第二个括号，则代价为 10，收益为 12，最大得分为 2。
示例3
输入
4
()()
-1 100 10 10
1000 101 100 100输出
789说明
最优操作位变成 "(())"。得分 990，代价为 201。
示例4
输入
2
()
-1 100
10 10输出
-10说明
如果放着不动，会直接亏 100，不如翻转一下主动亏 10
解题思路
官方题解写得什么鬼，完全看不懂。
注意到当把所有成对匹配的括号删去，那么剩余元素必然是 )...))((...( 的形式，即左部分全是 )（或空集），右部分全是 (（或空集）。把分界点记作 $k$，显然原序列的 $s_1 \sim s_k$ 中的 ( 只会与 $s_1 \sim s_k$ 中的 ) 匹配。同理原序列的 $s_{k+1} \sim s_n$ 中的 ) 只会与 $s_{k+1} \sim s_n$ 中的 ( 匹配。所以当分界点 $k$ 确定后左右两部分是独立的。
为此定义 $l_i$ 表示将 $s_1 \sim s_i$ 中的 ( 进行匹配使剩余元素均为 )（或空集）所能获得的最大得分，定义 $r_i$ 表示将 $s_i \sim s_n$ 中的 ) 进行匹配使剩余元素均为 (（或空集）所能获得的最大分数。
考虑如何通过 $l_{i-1}$ 转移得到 $l_i$。如果 $s_i$ 不会被匹配，那么就需要把 $s_1 \sim s_{i-1}$ 的 ( 匹配掉，再让 $s_i$ 变成 )，转移方程就有 $l_i = l_{i-1} + w_{i,1}$。这里的 $w_{i,0/1}$ 表示将 $s_i$ 变成 ( 或 ) 的代价（$0$ 或 $-c_i$）。否则如果 $s_i$ 与 $s_j$ 匹配，那么就需要把 $s_{j+1} \sim s_{i-1}$ 的括号都匹配完（显然 $i-j+1$ 应该为偶数），再让 $s_j$ 变 ( $s_i$ 变 )。先定义 $f(i,j)$ 表示将 $s_i \sim s_j$（长度为偶数）都匹配完所能获得的最大分数。因此转移方程就是 $l_i = l_{i-1} + \max\limits_{\begin{array}{c} 1 \leq j < i \\ i-j+1 \text{ is even} \end{array}}\left\{ f(j+1,i-1) + w_{j,0} + w_{i,1} + v_j \cdot v_i \right\}$。
综上有 $$l_i = \max\left\{l_{i-1} + w_{i,1},\;\; l_{i-1} + \max\limits_{\begin{array}{c} 1 \leq j < i \\ i-j+1 \text{ is even} \end{array}}\left\{ f(j+1,i-1) + w_{j,0} + w_{i,1} + v_j \cdot v_i \right\} \right\}$$
同理 $r_i$ 的转移方程为 $$r_i = \max\left\{r_{i+1} + w_{i,0},\;\; r_{i+1} + \max\limits_{\begin{array}{c} i < j \leq n \\ j-i+1 \text{ is even} \end{array}}\left\{ f(i+1,j-1) + w_{i,0} + w_{j,1} + v_i \cdot v_j \right\} \right\}$$
而 $f(i,j)$ 就是一个区间 dp。如果 $s_i$ 和 $s_j$ 匹配，那么转移方程就是 $f(i,j) = f(i+1,j-1) + w_{i,0} + w_{j,1} + v_i \cdot v_j$。否则由于 $s_i \sim s_j$ 都要匹配完，枚举 $k$，分别将 $s_{i} \sim s_k$ 和 $s_{k+1} \sim s_j$ 匹配完，转移方程就是 $f(i,j) = \max\limits_{i < k < j}\left\{ f(i,k) + f(k+1,j) \right\}$。
最后答案就是 $\max\limits_{0 \leq i \leq n}\left\{ l_i + r_{i+1} \right\}$。
AC 代码如下，时间复杂度为 $O(n^3)$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 505;
char s[N];
int v[N], c[N], w[N][2];
LL f[N][N], l[N], r[N];
int main() {
int n;
scanf("%d %s", &n, s + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", v + i);
}
for (int i = 1; i <= n; i++) {
scanf("%d", c + i);
if (s[i] == '(') w[i][1] = -c[i];
else w[i][0] = -c[i];
}
for (int len = 2; len <= n; len += 2) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
f[i][j] = f[i + 1][j - 1] + w[i][0] + w[j][1] + 1ll * v[i] * v[j];
for (int k = i + 1; k + 1 < j; k += 2) {
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
}
}
}
for (int i = 1; i <= n; i++) {
l[i] = l[i - 1] + w[i][1];
for (int j = i - 1; j >= 1; j -= 2) {
l[i] = max(l[i], l[j - 1] + f[j + 1][i - 1] + w[j][0] + w[i][1] + 1ll * v[j] * v[i]);
}
}
for (int i = n; i; i--) {
r[i] = r[i + 1] + w[i][0];
for (int j = i + 1; j <= n; j += 2) {
r[i] = max(r[i], r[j + 1] + f[i + 1][j - 1] + w[i][0] + w[j][1] + 1ll * v[i] * v[j]);
}
}
LL ret = -1e18;
for (int i = 0; i <= n; i++) {
ret = max(ret, l[i] + r[i + 1]);
}
printf("%lld", ret);
return 0;
}
参考资料
【题解】牛客练习赛124_PLUS：https://ac.nowcoder.com/discuss/1298659
标签：10,匹配,leq,max,括号,sim From： https://www.cnblogs.com/onlyblues/p/18162323