[2017 CCPC-Final][HDU 6249] Alice’s Stamps
[ 2018 Multi-University Training Contest 1 ] [ HDU6305 ] H RMQ Similar Sequence

[ 2018 Multi-University Training Contest 1 ] [ HDU6299 ] B Balanced Sequence

Zarxdy34 posted @ 2018年7月24日 13:55 in HDU with tags 贪心 , 26 阅读

        题意:将n个由'('和')'组成的字符串任意串接在一起,求从中能够取出的最长的满足括号匹配的子序列的长度。\(1 \leq n \leq 10^5 , 1 \leq |s_i| \leq 10^5 , \sum{|s_i|} \leq 5 \cdot 10^6\)。

        题解:将每个串中最长的满足括号匹配的序列全部取出来,剩下的部分就是形如\(")))((("\)这样的形式的,即一些右括号与一些左括号组成。记每个串这样处理出来后右括号数为a(就是左半边的括号数),左括号数为b,每个串都能表示成\( (a,b) \)的形式,接下来就是要对这些串排序使结果最优。

        考场上的做法基本上就是取多种排序方式求结果然后取最大值了。标算的排序做法是这样的:把串按照\(a < b\)和\( a \geq b\)分成两类,先取\( a < b\)的,在\( a < b\)这类中a小的先取,在\(a \geq b\)这类中b大的先取,然后扫一遍求出答案。大致证明一下:

        考虑交换相邻位置的两个串。考虑位于i和i+1的两个串,其中\( a_i \geq b_i \)且\( a_{i+1} < b_{i+1} \),交换两串不影响i之前的串,而在i+1之后的串,由于i+1之前左括号的总数在两串交换前后不会改变,且在i+1之后能够被使用的右括号也是固定且有限的,所以在交换i与i+1与不交换两种情况下的最优的策略一定是在i+1之前用掉最多的左括号的那个。设i之前剩下的左括号数为x,枚举所有情况,可以发现交换后更优(写起来不好写,式子大小不好比较,但是直接看很容易看出来,所以就懒得写了...)。同类情况考虑方法一样,比较容易,就不写了。

        然后根据大佬们的OI/ACM经验,这应该是全局最优的排序方法,于是按照这种方案排序做就好了。

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pair;
const int maxn=1e5+10;

char s[maxn];
Pair P[maxn];
int n,ans;

bool cmp(const Pair &a,const Pair &b)
{
	if ((a.first<a.second)>(b.first<b.second)) return true;
	if ((a.first<a.second)<(b.first<b.second)) return false;
	if (a.first<a.second) return a.first<b.first;
	else return a.second>b.second;
}

int main()
{
	int T;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&n);
		ans=0;
		for (int i=1;i<=n;i++)
		{
			scanf("%s",s);
			int len=strlen(s);
			int cl=0,cr=0;
			for (int j=0;j<len;j++)
			if (s[j]=='(') cl++;
			else if (cl) ans+=2,cl--;
			else cr++;
			P[i].first=cr;
			P[i].second=cl;
		}
		sort(P+1,P+1+n,cmp);
		for (int i=1,cl=0;i<=n;i++)
		{
			int tmp=min(cl,P[i].first);
			ans+=tmp<<1;
			cl+=P[i].second-tmp;
		}
		printf("%d\n",ans);
	}
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter