CF2261E What Does the Cow Say?

哦，Moo，Moo，Moo，我平时就会说这个！ —— Bessie 牛 Bessie 给你一个长度为 $n$ 的正规括号序列（RBS）$^{\text{∗}}$ 和一个整数 $k$。 你可以进行如下操作一次： - 选择一个下标 $i$（$1 \le i < n$），使得 $s_i s_{i+1} = \mathtt{()}$。 - 设 $s'$ 为将这两个字符从 $s$ 中移除后得到的字符串。 - 将 $s$ 赋值为 $\mathtt{(} + s' + \mathtt{)}$。 你最多可以进行 $k$ 次上述操作（可以为零次）。可以证明，每次操作后 $s$ 都仍然是一个正规括号序列。 一个 RBS 的分数被定义为该字符串中连续左括号“$\texttt{(}$”最多的个数。例如，字符串“$\texttt{(())((())())}$”的分数为 $3$。 你的任务是通过至多 $k$ 次操作，使分数最大。 $^{\text{∗}}$ 一个正规括号序列是指可以通过在原括号序列中插入字符 $1$ 和 $+$，使之变为一个正确的算术表达式。例如： - 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是正规括号序列（结果表达式为 $\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$）； - 括号序列 $\texttt{)(}$、$\texttt{(}$ 和 $\texttt{)}$ 不是正规括号序列。

每组测试包含多组测试用例。第一行为测试用例组数 $t$（$1 \le t \le 10^4$）。接下来每组输入如下： 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 4 \cdot 10^5$，$0 \le k \le \frac{n}{2}$）——RBS 的长度以及最多可操作次数。 第二行包含长度为 $n$ 的字符串 $s$，仅包含字符“$\texttt{(}$”与“$\texttt{)}$”——给定的正规括号序列。 保证 $s$ 是正规括号序列，所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^5$。

每组测试用例输出一行，每行一个整数，表示通过至多 $k$ 次操作可以获得的最大分数。

在第一个测试用例中，我们无法进行任何操作。最多连续的左括号数为 $1$。 在第三个测试用例中，我们可以选 $i = 1$，操作后 $s = \texttt{(()())}$。然后选 $i = 4$，操作后 $s = \texttt{((()))}$。共用了 2 次操作，分数为 $3$，是最大可能分数。 在第七个测试用例中，可以选择 $i = 6$，操作后得到 $\texttt{(()(((((()))))))}$，它的分数为 $6$。可以证明 $6$ 是最大可能分数。 由 ChatGPT 5 翻译