[ HDU6299 ] Balanced Sequence

        题意:将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经验,这应该是全局最优的排序方法,于是按照这种方案排序做就好了。


page views : 5 views

发表评论

电子邮件地址不会被公开。 必填项已用*标注