#P18232. Brackets
Brackets
Brackets
给定一个长度为 的字符串 ,其中只含四种括号:圆括号 ()、方括号 []、花括号 {} 和尖括号 <>。
合法括号串递归定义如下:
- 空串是合法括号串。
- 若 是合法括号串,则它们的拼接 也是合法括号串。
- 若 是合法括号串,则 、、、 都是合法括号串。
另给出 个区间 。第 个对象是子串 ,下标从 开始。
你可以将这些对象中的若干个分成若干对。每一对包含两个不同编号的对象,而且每个对象最多出现在一对中。对于每一对,可以自行选择两个对象的先后顺序;按该顺序拼接得到的字符串必须是合法括号串。
求最多能得到多少对。
即使两个区间完全相同,它们仍是不同编号的对象,可以分别使用。区间之间允许重叠;限制针对对象编号,而非原串中的字符位置。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例:
- 第一行两个整数 。
- 第二行一个长度为 的字符串 。
- 接下来 行,第 行两个整数 。
数据范围:
- ;
- ;
- ;
- 中每个字符均属于四种左右括号;
- 同一输入文件所有测试用例的 之和不超过 , 之和也不超过 。
输出格式
每个测试用例输出一行一个整数,表示最多得到的对数。
样例
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
0
3
0
2
第一个测试用例只有一个对象,即使该对象本身是合法括号串,也无法组成一对。
第二个测试用例中,三个对象是右圆括号,另外三个对象是左圆括号。每个左圆括号与一个右圆括号配对,按先左后右的顺序拼接,可以得到三对。
第三个测试用例的两个对象分别为 ([) 和 (]),无论按哪种顺序拼接,都不是合法括号串。
第四个测试用例的一种最优选择是将第 个对象配成一对,第 个对象配成一对;每对内部按这些编号的顺序拼接即可。