自动搬运

查看原文

来自洛谷，原作者为

	XHY20180718 不拿 7 级钩不改个签

搬运于2025-08-24 22:54:49，当前版本为作者最后更新于2024-01-29 13:55:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本来觉得这题挺不错的，但数据被暴力草过去了，所以给 $7$ 分。

简要题意：

给你一个括号序列和 $\{a\}$ 数组，将其分成连续的若干组。

每个组的权值：若括号序列合法，则为 $a_r-a_l$，否则为 $0$。

求组的权值之和的最大值。

主要思路：

先写暴力，设 $f_i$ 表示在当前位置 $i$ 后分组 $1\sim i$ 之间所有组的最大权值。

易得转移方程：

$$f_i=\max_{j=1}^{i-1}\{f_j+w_{i,j}\}$$

我们将合法与不合法情况分开来讨论：

当我们从不合法情况来转移时：

$$f_i=\max_{[j+1,i]\text{为非法区间}}\{f_j\}$$

由于 $f_i$ 本身单调递增，所以说：

$$f_i=f_{i-1}$$

而当我们从合法的情况来转移时：

$$f_i=(\max_{[j+1,i]\text{为合法区间}}\{f_j-a_{j+1}\})+a_i $$

于是我们将 $f_j-a_{j+1}$ 打包，因为其对于每个 $j$ 都是不变的。

对于每一个 $i$，用 $c_i$ 来维护他：

$$c_i=\max_{j|[j+1,i]\text{为合法区间}}\{f_j-a_{j+1}\}$$

将上面两种情况比较即可，也就是说：

$$f_i=\max \{c_i+a_i,f_{i-1}\}$$

接下来要讨论的问题是如何快速算出 $c_i$：

设 $A$，$B$ 为合法括号序列，则所有合法括号序列满足以下情况：

1. $()$，最基本的括号序列。
2. $(A)$，一个括号将一个合法括号序列括起来依然是合法括号序列。
3. $AB$，两个合法括号序列拼起来依然是合法括号序列。

对于作为一个右括号的 $S_i$ 来说，我们完全可以通过栈找出与他合起来的最近左括号，其位置记为 $lst_i$。

所以，对于一个 $i$，我们完全可以找出 $lst_i$，除了第三种情况都可以解决，然后就能套上面的式子，给 $c_i$ 赋初值：$f_{lst_{i-1}}-a_{lst_i}$。

而对于第三种情况，由于两个括号序列可以合成一个新序列，那我们的 $c_i$ 就能从 $c_{lst_i-1}$ 转移过来，因为集合 $j|[j+1,i]\text{为合法区间}$ 将严格包含集合 $j|[j+1,lst_i-1]\text{为合法区间}$，唯一多的元素便是 $lst_i$。

所以：

$$c_i=\max\{c_{lst_i-1},f_{lst_{i-1}}-a_{lst_i}\}$$

结合：

$$f_i=\max\{c_i+a_i,f_{i-1}\}$$

于是这题我们就做完了。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+5,inf=1e18;
int n,a[N],lst[N],r;
int f[N],st[N],c[N];
bool b[N];
string S;
signed main(){
    // freopen("test.in","r",stdin);
    // freopen("std.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>S;
    for(int i=1; i<=n; ++i)
        cin>>a[i],b[i]=(S[i-1]=='(');
    for(int i=1; i<=n; ++i)
        if(!b[i]&&r)lst[i]=st[r--];
        else if(b[i])st[++r]=i;
    for(int i=0; i<=n; ++i)
        f[i]=c[i]=-inf;f[0]=0;
    for(int i=1; i<=n; ++i){
        f[i]=f[i-1];
        if(lst[i]){
            c[i]=max(c[lst[i]-1],f[lst[i]-1]-a[lst[i]]);
            f[i]=max(c[i]+a[i],f[i]);
        }
    }cout<<f[n];
    return 0;
}