#P7221. [2023省队模拟]括号
[2023省队模拟]括号
题目描述
合法的括号串递归定义如下:
- 空串合法。
- 若 是合法串,则在其两端各加一个相匹配的括号后得到的串也合法。
- 若 都是合法串,则将它们拼接得到的串也合法。
给出一个长度为 的括号串。第 个字符对应参数 。
每次操作可以翻转一个字符,即把左括号变成右括号,或把右括号变成左括号。要求进行尽量少的操作,使得到的括号串同时满足以下两个条件:
- 删除所有 的字符后,剩下的括号串合法。
- 删除所有 的字符后,剩下的括号串合法。
两次删除分别作用于同一个修改后的字符串。
输入格式
第一行一个正整数 。
第二行一个长度为 的括号串。
第三行 个整数 。
输出格式
输出最少操作次数。如果无解,输出 。
样例输入 1
5
))))(
0 1 2 2 2
样例输出 1
4
例如,将括号串修改为 (()()。
样例输入 2
6
(()())
0 0 0 0 0 0
样例输出 2
0
样例输入 3
3
()(
0 2 1
样例输出 3
-1
样例输入 4
15
()))(()((((())(
0 2 2 1 2 2 1 2 1 1 1 1 1 1 1
样例输出 4
7
数据范围与约定
对于所有数据,。
| 子任务 | 数据范围 | 分值 |
|---|---|---|
| 1 | 10 | |
| 2 | 20 | |
| 3 | 所有 | 10 |
| 4 | 30 | |
| 5 | 无特殊限制 |