CF1821E Rearrange Brackets

一个“正规括号序列”是指可以通过在序列的原有字符之间插入字符 $1$ 和 $+$，将其转化为一个合法算术表达式的括号序列。例如： - 括号序列 "()()" 和 "(())" 是正规括号序列（对应的表达式分别为 "(1)+(1)" 和 "((1+1)+1)"）； - 括号序列 ")(", "(" 和 ")" 不是正规括号序列。 现在给你一个正规括号序列。每次操作，你可以移除一对相邻的括号（左边是左括号，右边是右括号），然后将剩余部分按原顺序拼接。该操作的代价是这对括号右括号右侧剩余括号的数量。 一个正规括号序列的总代价定义为：将序列变为空所需操作的总代价最小值。 实际上，你并不会移除任何括号。你会得到一个正规括号序列和一个整数 $k$。你最多可以进行 $k$ 次如下操作： - 从序列中取出某个括号，并将其插入到任意位置（可以插入到任意两个括号之间、开头或结尾，也可以放回原位）。 所有操作完成后，括号序列仍需保持正规。请问，经过最多 $k$ 次操作后，所得正规括号序列的最小总代价是多少？

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $k$（$0 \le k \le 5$），表示你最多可以进行的操作次数。 每个测试用例的第二行给出一个非空的正规括号序列，仅包含字符 '(' 和 ')'。 所有测试用例中括号序列的总长度不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示经过最多 $k$ 次操作后，所得正规括号序列的最小总代价。

由 ChatGPT 4.1 翻译