括号序列的代价

ID: 18544

传统题

2000ms

512MiB

显示难度暂无评定

上传者:

标签>

动态规划

贪心

暴力

题目描述

定义任意括号字符串的代价为：该字符串中，是合法括号子序列的最长子序列的长度。

给你一个括号字符串 $s$ 和整数 $k$ 。你最多可以从字符串 $s$ 中删除 $k$ 个字符，要求让处理后字符串的代价尽可能小。

子序列定义：序列 $a$ 是序列 $b$ 的子序列，当且仅当可以通过从 $b$ 中删除若干（可以为0或全部）任意位置的元素得到 $a$ 。

合法括号序列定义：向该序列中插入 + 和 1 可以得到合法算术表达式。例如 (())()、()、(()(())) 是合法的；) (、(()、(()))( 不是合法的。

本题包含多组测试用例。第一行输入测试用例数量 $t$ （ $1 \le t \le 10^3$ ）。

每组测试用例：第一行两个整数 $n,k$ （ $1 \le n \le 5000;\ 0 \le k \le n$ ），分别代表字符串 $s$ 的长度和最多可删除字符数量。第二行给出长度为 $n$ 的字符串 $s$ ，仅由字符 ( 和 ) 构成。

附加约束：所有测试用例的 $n$ 总和不超过 $5000$ 。

对每组测试用例，输出一个长度为 $n$ 的二进制字符串。第 $i$ 位为 1 代表原字符串对应位置字符被删除，0 代表保留。串中 1 的数量不能超过 $k$ 。删除标记对应的剩余字符串的代价要做到最小。存在多解时输出任意一组合法答案。

10
2 1
)(
2 0
()
4 1
(())
4 1
())(
5 1
((())
6 2
()()()
6 2
(()())
6 2
())(()
7 3
(()((()
10 3
(()())())(

第一组测试用例，字符串本身代价已经是 $0$ ，因此不需要删除任何字符。

第三组测试用例，删除一个字符后无法把代价降到 $0$ ，但删除任意一个字符都可以得到代价为 $2$ 的字符串。