洛谷P10115题解

题意简述

给定一个括号序列，求整个序列的美丽值最大。

思维路径

见到序列和权值，很容易想到需要用 DP。

我们定义 \(f[i][j]\) 表示第 \(1\) 到 \(i\) 个括号产生的美丽值最大值，其中 \(j=0\) 表示第 \(i\) 个括号本身不参与美丽值贡献，\(j=1\) 表示第 \(i\) 个括号本身参与美丽值贡献。

接下来分情况讨论。

若 \(j=0\) 说明 \(i\) 本身就不参与美丽值增加，贡献为 \(0\)，因此可以得到转移方程 \(f[i][0]=\max_{0\le j \le 1}{f[i-1][j]}\)。

若 \(j=1\) 说明 \(i\) 本身参与美丽值增加，定义产生贡献的括号序列为 \(u\) 到 \(i\)，要求这一段括号序列为合法的。定义 \(p[i]\)表示与 \(i\) 匹配的括号，那么 \(u\) 的第一个取值为 \(p[i]\)，之后可以通过 \(u=p[u-1]\) 遍历所有可能的转移。由此可以得到转移方程 \(f[i][1]=\max_{0\le j \le 1}{f[u][j]}\)。

实现细节

\(j=1\) 的情况种遍历 \(u\) 的方式仍然是需要较长时间的，我们定义一个数组 \(mx[i]\) 表示 \(i\) 之前可能作为转移的值中的最大值。

假设当前 \(f[i][1]\) 的转移遍历到 \(u\)，若 \(mx[u-1]+a[i] \le f[i][1]\)，则可以证明此时的 \(f[i][1]\) 一定是最大值，可以停止遍历。

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=4000009;
const ll INF=1e18+9;
ll n,a[N],f[N][2],p[N],stk[N],nT,mx[N];
string s;

void input(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	cin>>s;
	for(ll i=1;i<=n;i++) cin>>a[i];
}

void solve(){
	for(ll i=0;i<(ll)s.size();i++){
		if(s[i]=='('){
			stk[++nT]=i+1;
		}
		else if(nT>0){
			p[i+1]=stk[nT];
			nT--;
		}
	}
	for(ll i=1;i<=n;i++){
		if(p[i]!=0){
			ll u=p[i];
			while(u){
				f[i][1]=max(f[i][1],max(f[u-1][1],f[u-1][0])+a[i]-a[u]);
				u=p[u-1];
				if(mx[u]+a[i]<=f[i][1]) break;
			}
		}
		mx[i]=max(mx[i-1],f[i][1]);
		f[i][0]=max(f[i-1][1],f[i-1][0]);
		mx[i]=max(mx[i],f[i][0]);
	}
	cout<<mx[n];
}

int main(){
	input();
	solve();
	return 0;
}