#P6621. 「PA 2022」Nawiasowe podziały

    ID: 6472 传统题 1000ms 1024MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS排序与序列处理一维前缀和离线与分治分治算法数据结构ST 表动态规划树形 DP凸包优化 DPWQS 二分数值计算与优化凸性/单峰性判定CF3200

「PA 2022」Nawiasowe podziały

「PA 2022」Nawiasowe podziały

题目描述

我确信你是知道括号序列的,但是以防万一,并且作为回顾,让我们回忆一下它的定义:

  • () 是一个合法的括号序列。
  • 如果 SS 是一个合法的括号序列,那么 (S) 也是一个合法的括号序列。
  • 如果 S1S_1 和 S2S_2 都是合法的括号序列,那么 S1S2S_1S_2 也是一个合法的括号序列。
  • 不符合上述规则的括号序列都不是合法的括号序列。

给出一个长度为 nn 且仅由字符 ( 和 ) 组成的字符串,以及一个数字 kk,这个字符串不一定是合法的括号序列。你的任务是把它分成 kk 个非空段(每个字符必须恰好属于一段内),使得每段中是合法括号序列的子串个数之和最小。

这里的子串是段内连续的一段字符,并按出现位置计数:即使两个合法括号子串的内容相同,只要起止位置不同,就分别计数。空串不计入。划分出的 kk 段本身可以不是合法括号序列;跨越分段边界的子串不计入任何一段。

输入格式

第一行两个整数 n,k (1≤k≤n≤100 000)n,k\ (1\le k\le n\le 100\ 000),分别表示字符串长度和要分成的段数。

第二行一个长度为 nn 的字符串,保证字符串仅由 ( 和 ) 组成。

输出格式

输出一行一个整数,表示所有段中是合法括号序列的子串个数之和的最小值。

样例输入 1

15 2
())(()())()(())

样例输出 1

6

样例输入 2

15 3
())(()())()(())

样例输出 2

3

数据范围与提示

  • 某些子任务满足 n≤18n\le 18。
  • 某些子任务满足 n≤300n\le 300。
  • 某些子任务满足 n≤4 000n\le 4\ 000。
  • 某些子任务满足 k≤30k\le 30。

对于上面提到的每种情况,都存在至少一个子任务满足。这些子任务满足条件可能不相交,也可能相交。