好哥哥

给定一段合法括号序列和 $n$ 元钱，合法括号序列的定义如下：

1. $()$ 是合法的括号序列。

2.若字符串 $A$ 是合法的括号序列，那么 $(A)$ 也是合法的括号序列。

3.若字符串 $A$ , $B$ 是合法的括号序列，那么 $AB$ 也是合法的括号序列。

我们设定 $G_{x}$ 表示第 $x$ 对括号的层数，即：它前面有多少未匹配的左括号。同时规定一对括号 $A$ 是另一对括号 $B$ 的好哥哥，当且仅当 $G_{A}=G_{B}+1$ 且括号 $A$ 在括号 $B$ 内。

如果当前位于一对括号 $Q$ ，每次可以花费 $1$ 元跳到：

1. 它的任意一个好哥哥。

2. 一对括号 $X$ ，要求 $X$ 的好哥哥是 $Q$ 。

假如一开始位于第一对括号，请问最多可以经过多少对不重复的括号？

#include<bits/stdc++.h> using namespace std; int v,n,cnt; int main(){ scanf("%d%d\n",&v,&n); int s=0,ma=0; for(int i=1;i<=2*v;i++){ if(getchar()=='(')s++; else s--,cnt++; ma=max(ma,s); if(s==0)break; } if(n<=ma-1){ cout<<n+1; return 0; } else cout<<min(cnt,(int)(n-ma+1)/2+ma); return 0; }

v, n = map(int, input().split()) a = input() s, num, mx, ans = 0, 0, 0, 0 for i in range(0, 2 * v): if a[i] == '(': s, num = s + 1, num + 1 else: s -= 1 if s == 0: break mx = max(mx, s) if n + 1 < num: num = n + 1 ans = min(num, mx + (n + 1 - mx) // 2) print(ans)

详情