← 返回题目列表

Codeforces · 1997/C

C. 偶数位置

中文机器翻译题面 查看原题

Monocarp 有一个规则的括号序列 $$$s$$$,长度为 $$$n$$$($$$n$$$ 是偶数)。他甚至想出了自己的方法来计算其成本。

他知道在常规括号序列(RBS)中,每个左括号与相应的右括号配对。因此,他决定将 RBS 的成本计算为相应括号对之间的距离之和。

例如,让我们看一下 RBS (())()。它有三对括号:

- (__)__: $$$1$$$ 位置和 $$$4$$$ 位置括号之间的距离为 $$$4 - 1 = 3$$$;
- _()___: 距离为 $$$3 - 2 = 1$$$;
- ____():距离为 $$$6 - 5 = 1$$$。

不幸的是,由于数据损坏,Monocarp 丢失了奇数位置 $$$s_1、s_3、\dots、s_{n-1}$$$ 上的所有字符。仅保留偶数位置上的字符 ($$$s_2, s_4, \dots, s_{n}$$$)。例如,(())() 变成了_(_)_)。

Monocarp 希望通过在奇数位置上放置括号来恢复他的 RBS。但由于恢复的苏格兰皇家银行可能不是唯一的,他想选择一个成本最小的。单靠 Monocarp 来说太难了,你能帮助他吗?

提醒:常规括号序列是仅由括号组成的字符串,因此,当插入 1-s 和 +-s 时,该序列会给出有效的数学表达式。例如,()、(()) 或 (()())() 是 RBS,而 )、()( 或 ())(() 则不是。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。接下来的 $$$t$$$ 案例如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n$$$ 是偶数) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,其中奇数位置上的所有字符都是“_”,偶数位置上的所有字符都是“(”或“)”。

附加限制:

- $$$s$$$ 可以恢复为至少一个正则括号序列;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 通过用括号替换 '_'-s 可以从 $$$s$$$ 获得常规括号序列的最小成本。

示例

输入 #1

4
6
_(_)_)
2
_)
8
_)_)_)_)
8
_(_)_(_)

输出 #1

5
1
4
8

注意

在第一个测试用例中,最好使 $$$s$$$ 等于 (())()。 $$$s$$$ 的成本将等于 $$$3 + 1 + 1 = 5$$$。

在第二个测试用例中,唯一的选择是使 $$$s$$$ 等于 (),成本为 $$$1$$$。

在第三个测试用例中,唯一可能的 RBS 是 ()()()(),成本为 $$$1 + 1 + 1 + 1 = 4$$$。

在第四个测试用例中,最佳方案是使 $$$s$$$ 等于 (())(()),成本为 $$$3 + 1 + 3 + 1 = 8$$$。