题解

思路

正规括号序列的代价等于扫描时每个左括号出现前的当前余额之和。把一次移动看成先从原位置删去一个括号，再在扫描过程中的某处插入这个括号。

做法

由于至多移动 $k\le5$ 个字符，扫描原串时只需记录：已删但尚未插回的左括号数、右括号数，以及已使用的移动次数。这两个括号数相对初始偏移至多为 $k$，状态范围均为 $[0,2k]$。

在每个位置可以插入一个此前删去的左括号或右括号，也可以正常保留当前字符，或者把当前字符标记为删去。根据原串当前余额和两个偏移可算出新串当前余额；插入或保留左括号时把该余额加入代价，右括号则要求余额为正。最后两个偏移都回到初始值，取使用不超过 $k$ 次的最小代价。

$k=0$ 时直接扫描并累加每个左括号前的余额。小规模可广度枚举每次移动后得到的不同字符串。

复杂度

时间复杂度 $O(nk^3)$，空间复杂度 $O(k^3)$。