P10115 题解（2023 激励计划评分 7）

· · 题解

本来觉得这题挺不错的，但数据被暴力草过去了，所以给 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 为合法括号序列，则所有合法括号序列满足以下情况：

对于作为一个右括号的 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;
}