AT_abc407_e [ABC407E] Most Valuable Parentheses-EW帮帮网

AT_abc407_e [ABC407E] Most Valuable Parentheses

洛谷题目传送门

ATcoder题目传送门

题目描述

给你一个长度为 $2 N$ 的数列 $A$ 。

定义一个长度为 $2 N$ 的括号序列 $s$ 的得分：

对于所有 $s_i=$ )， $A_i\leftarrow 0$ ；
得分为上述操作后 $A$ 中所有元素之和。

请求出对于一个长为 $2 N$ 的合法的括号序列 $s$ ，它的得分的最大值。一个括号序列是合法的当且仅当它可以通过多次删去子段 () 变为空串。

输入格式

多组数据。第一行一个整数 $T(1\le T\le 500)$ 表示数据组数。

对于每组数据：
第一行一个整数 $N(1\le N\le 2\times 10^5)$ 。
接下来 $2 N$ 行，每行一个数字，依次为 $A_1,A_2,\cdots,A_{2N}(0\le A_i\le 10^9)$ 。

保证单个测试点内 $\sum N\le 2\times 10^5$ 。

输出格式

对于每组数据，输出一行一个整数表示答案。***

输入输出样例 #1

输入 #1

输出 #1

1200
6000000000

说明/提示

样例解释 1

在第一组数据中， $s =$ (())() 的得分为 $400 + 500 + 0 + 0 + 300 + 0 = 1200$ 。可以证明这是可能获得的最大的分，故答案为 $1200$ 。

如第二组数据所示，答案可能超出 32 位整数的表示范围。

By @chenxi2009

思路详解

思路引入

首先，我们先来思考一下如何判断合法的括号序列。首先显然左括号数量要等于右括号数量，但是这还不够。回想我们之前做的判断合法括号序列的题，我们还可以得出一个条件： $\forall i\epsilon[1,n],sum_{(,i}>=sum_{),i}$ 。这是很显然的，因为左右括号要对应。

现在我们来考虑一下如何求解这道题。根据 $N$ 的范围，我们发现1维 $d p$ 不好转移，那就只能2维 $d p$ 了，可是2维 $d p$ 会超。所以我们先将 $d p$ 放一放，考虑能否用贪心。

首先，我们肯定不能考虑让左括号尽量多，因为我们又不是求左括号的最大值。我们想要的是左括号上的值尽量大，那我们先尽量选右括号，当右括号多了的时候，我们在从区间中选取最大值，将其改为最括号即可。这样得到的答案一定是最优的，而且我们还同时维护了括号序列合法。

过程分析

我们的具体过程如下：

先建立一个大根堆维护最大值。
从1开始枚举 $i$ ，将a_{i}入堆，假如当前的右括号数量+1大于了左括号数量，则选取最大值，将其改为左括号。
否则将当前设为右括号。

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4e5+5;
ll T;
ll a[N];
int main(){
//先来思考如何判定一个括号序列是合法的
//首先肯定'(',')'要各占一半，但这个条件显然不够
//还有就是对于任意i，都要满足在1-i中左括号的和大于等于右括号的和
//那对于每个区间，我们让左括号尽量多是不对的，因为我们无法保证后面的
//那我们就尽量让右括号多，这样最基本的左括号最多，我们在这里将左括号给最大值即可
	cin>>T;
	while(T--){
		ll n;
		cin>>n;n*=2;
		ll ans=0;
		for(ll i=1;i<=n;i++)cin>>a[i];
		ll js=0;
		priority_queue<ll>q;
		for(ll i=1;i<=n;i++){
			q.push(a[i]);
			if(js+1>i-(js+1)){
				ans+=q.top();q.pop();
			}
			else js++;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

AT_abc407_e [ABC407E] Most Valuable Parentheses