Home => ProblemSet => 括号匹配
2382: 括号匹配
Time Limit: 1 Sec Memory Limit: 512 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
令 s[i:j]=sisi+1…sj，表示 s 的第 i 个到第 j 个字符组成的子串。
空串是合法括号序列。若 t 合法，则 (t)、[t]、{t}、<t> 均合法。若 u,v 合法，则拼接得到的 uv 也合法。除此之外，没有其他合法括号序列。
例如，([]) 与 [<>{{}}] 合法，(][) 不合法。
给定由 ()[]{}<> 组成的字符串 S 与若干个数对 (l,r)。
每个数对至多使用一次。将数对两两配对，使每对的两个子串按某种顺序拼接后成为合法括号序列。求最多能配成多少对。
空串是合法括号序列。若 t 合法，则 (t)、[t]、{t}、<t> 均合法。若 u,v 合法，则拼接得到的 uv 也合法。除此之外，没有其他合法括号序列。
例如，([]) 与 [<>{{}}] 合法，(][) 不合法。
给定由 ()[]{}<> 组成的字符串 S 与若干个数对 (l,r)。
每个数对至多使用一次。将数对两两配对，使每对的两个子串按某种顺序拼接后成为合法括号序列。求最多能配成多少对。
Input
第一行输入数据组数 T，每组数据的格式如下：
第一行输入两个整数 n,m，分别表示 S 的长度与数对的个数。 第二行输入字符串 S。 此后的 m 行，每行两个整数 l,r，表示一个数对。
第一行输入两个整数 n,m，分别表示 S 的长度与数对的个数。 第二行输入字符串 S。 此后的 m 行，每行两个整数 l,r，表示一个数对。
Output
每组数据输出一个整数，表示最大的组数。
Sample Input Copy
4
8 1
()[]{}<>
3 6
2 6
)(
1 1
1 1
1 1
2 2
2 2
2 2
6 2
([)(])
1 3
4 6
22 8
([{}<<<<])>>>>([]){()}
3 8
11 14
1 10
3 4
19 22
20 21
17 20
21 22
Sample Output Copy
0
3
0
2
HINT
样例二：
输入：
1
4 4
([])
1 2
3 4
2 3
1 4
输出：
2
其他样例：brackets-samples.zip
输入：
1
4 4
([])
1 2
3 4
2 3
1 4
输出：
2
样例 1 解释
第一组数据中，[]{} 自身合法，但没有配对对象，答案为 0。第二组数据中，三个 ) 分别与三个 ( 拼成 ()，答案为 3。第三组数据无法分组。第四组数据可以配对第 1、2 项，得到 {}<<<< 与 >>>>；配对第 4、5 项，得到 {} 与 {()}。因此答案为 2。样例 2 解释
前两个子串为 ([ 和 ])，拼接后得到 ([])。后两个子串分别为 [] 和 ([])，也能拼成合法括号序列。 其他样例：brackets-samples.zip