CF2261E.What Does the Cow Say?
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Oh, Moo, Moo, Moo, I speak that normally!
— Bessie the Cow
Bessie gives you a regular bracket sequence (RBS)∗ of length n and an integer k.
In one operation, you can do the following:
- Choose an index i (1≤i<n) such that sisi+1=().
- Let s′ denote the string obtained after removing these two characters from s.
- Set s:=(+s′+).
You may perform this operation at most k times (possibly zero). It can be shown that s remains an RBS after every such operation.
The score of an RBS is defined as the maximum number of consecutive opening brackets '(' in the string. For example, the score of the string "(())((())())" is 3.
Your task is to find the maximum possible score you can obtain by performing at most k operations on the given string.
∗A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting the characters 1 and + between the original characters of the sequence. For example:
- bracket sequences ()() and (()) are regular (the resulting expressions are: (1)+(1) and ((1+1)+1));
- bracket sequences )(, ( and ) are not.
哦,哞,哞,哞,我平时就这么说话!
——奶牛贝茜
贝茜给你一个长度为 n 的正则括号序列(RBS)∗ 和一个整数 k。
在一次操作中,你可以执行以下步骤:
- 选择一个下标 i(满足 1≤i<n),使得 sisi+1=();
- 记 s′ 为从 s 中删去这两个字符后所得的字符串;
- 令 s:=(+s′+)。
你最多可执行该操作 k 次(也可以不执行)。可以证明:每次执行该操作后,s 仍为一个 RBS。
一个 RBS 的得分定义为该字符串中连续左括号 '(' 的最大个数。例如,字符串 "(())((())())" 的得分为 3。
你的任务是:对给定字符串最多执行 k 次上述操作,求所能得到的最大可能得分。
∗ 正则括号序列(Regular Bracket Sequence, RBS)是指:通过在原序列的字符之间插入数字 1 和加号 +,可将其转化为一个合法算术表达式的括号序列。例如:
- 括号序列 ()() 和 (()) 是正则的(对应表达式分别为:(1)+(1) 和 ((1+1)+1));
- 括号序列 )(、( 和 ) 则不是。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤104). The description of the test cases follows.
The first line of each test case contains two integers n and k (2≤n≤4⋅105, 0≤k≤2n) — the length of the RBS and the maximum number of operations you may perform.
The second line of each test case contains a string s of length n consisting of characters '(' and ')' — the given RBS.
It is guaranteed that s is a regular bracket sequence, and that the sum of n over all test cases does not exceed 4⋅105.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤104)。随后是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 k(2≤n≤4⋅105,0≤k≤2n)——分别表示该规则括号序列(RBS)的长度以及你最多可执行的操作次数。
每个测试用例的第二行包含一个长度为 n 的字符串 s,其仅由字符 '(' 和 ')' 组成——即给定的 RBS。
保证 s 是一个规则括号序列,且所有测试用例中 n 的总和不超过 4⋅105。
输出格式
For each test case, print a single integer — the maximum score you can obtain by performing at most k operations.
对于每个测试用例,输出一个整数——即最多执行 k 次操作所能获得的最大得分。
输入输出样例
输入#1
9 2 0 () 4 1 (()) 6 2 ()()() 8 1 ()((())) 8 3 (()())() 12 4 ((()())())() 16 1 ()(((()((()))))) 22 1 ((((()()(())((())))))) 28 0 (((()(((())()((())))())))())
输出#1
1 2 3 4 4 6 6 6 4
说明/提示
In the first test case, we cannot perform any operations. The maximum number of consecutive opening brackets is 1.
In the third test case, we can choose index i=1, performing the operation gives us $s = $ "(()())". Then, choosing index i=4 gives us $s = $ "((()))". We used 2 operations and got a score of 3, which is the maximum possible score.
In the seventh test case, we can choose index i=6, performing the operation gives us $s = $ "(()(((((()))))))", which has a score of 6. It can be shown that 6 is the maximum possible score achievable.
在第一个测试用例中,我们无法执行任何操作。连续左括号的最大数量为 1。
在第三个测试用例中,我们可以选择索引 i=1,执行操作后得到 $s = $ "(()())"。接着选择索引 i=4,得到 $s = $ "((()))"。我们共使用了 2 次操作,获得了 3 分,这是可能达到的最高得分。
在第七个测试用例中,我们可以选择索引 i=6,执行操作后得到 $s = $ "(()(((((()))))))",其得分为 6。可以证明,6 是能够达到的最高得分。
输入解题思路,AI测评打分。不知道怎么写?