#P7221. [2023省队模拟]括号

    ID: 7055 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400贪心枚举前缀和字符串构造区间DP计数DP

[2023省队模拟]括号

题目描述

合法的括号串递归定义如下:

  • 空串合法。
  • 若 SS 是合法串,则在其两端各加一个相匹配的括号后得到的串也合法。
  • 若 S,TS,T 都是合法串,则将它们拼接得到的串也合法。

给出一个长度为 nn 的括号串。第 ii 个字符对应参数 ci∈{0,1,2}c_i\in\{0,1,2\}。

每次操作可以翻转一个字符,即把左括号变成右括号,或把右括号变成左括号。要求进行尽量少的操作,使得到的括号串同时满足以下两个条件:

  • 删除所有 ci=0c_i=0 的字符后,剩下的括号串合法。
  • 删除所有 ci=1c_i=1 的字符后,剩下的括号串合法。

两次删除分别作用于同一个修改后的字符串。

输入格式

第一行一个正整数 nn。

第二行一个长度为 nn 的括号串。

第三行 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。

输出格式

输出最少操作次数。如果无解,输出 −1-1。

样例输入 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

数据范围与约定

对于所有数据,n≤6000n\le6000。

子任务 数据范围 分值
1 n≤20n\le20 10
2 n≤300n\le300 20
3 所有 ci=0c_i=0 10
4 n≤2000n\le2000 30
5 无特殊限制