#P6621. 「PA 2022」Nawiasowe podziały
「PA 2022」Nawiasowe podziały
「PA 2022」Nawiasowe podziały
题目描述
我确信你是知道括号序列的,但是以防万一,并且作为回顾,让我们回忆一下它的定义:
()是一个合法的括号序列。- 如果 是一个合法的括号序列,那么
(S)也是一个合法的括号序列。 - 如果 和 都是合法的括号序列,那么 也是一个合法的括号序列。
- 不符合上述规则的括号序列都不是合法的括号序列。
给出一个长度为 且仅由字符 ( 和 ) 组成的字符串,以及一个数字 ,这个字符串不一定是合法的括号序列。你的任务是把它分成 个非空段(每个字符必须恰好属于一段内),使得每段中是合法括号序列的子串个数之和最小。
这里的子串是段内连续的一段字符,并按出现位置计数:即使两个合法括号子串的内容相同,只要起止位置不同,就分别计数。空串不计入。划分出的 段本身可以不是合法括号序列;跨越分段边界的子串不计入任何一段。
输入格式
第一行两个整数 ,分别表示字符串长度和要分成的段数。
第二行一个长度为 的字符串,保证字符串仅由 ( 和 ) 组成。
输出格式
输出一行一个整数,表示所有段中是合法括号序列的子串个数之和的最小值。
样例输入 1
15 2
())(()())()(())
样例输出 1
6
样例输入 2
15 3
())(()())()(())
样例输出 2
3
数据范围与提示
- 某些子任务满足 。
- 某些子任务满足 。
- 某些子任务满足 。
- 某些子任务满足 。
对于上面提到的每种情况,都存在至少一个子任务满足。这些子任务满足条件可能不相交,也可能相交。