题解 CF1452C 【Two Brackets】
Published:
一个显然的结论，当我们可以同时删去多个合法的括号匹配的时候，分多次删除一定更优。同时，当我们删去一些合法的括号匹配时，不会改变剩下的括号匹配的合法性。因此，找出所有的合法括号匹配即可。
#include<bits/stdc++.h>
#define re register
#define ll long long
#define LL inline ll
#define I inline int
#define V inline void
#define B inline bool
#define FOR(i,a,b) for(re int i=(a),i##i=(b);i<=i##i;++i)
#define ROF(i,a,b) for(re int i=(a),i##i=(b);i>=i##i;--i)
#define gc getchar()
using namespace std;
const int N=2e5+10;
LL read(){
ll p=0; bool w=0; char ch=gc;
while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
return w?-p:p;
}
int T,len,ans,s,t;
char ch[N];
int main(){
T=read();
while(T--){
scanf("%s",ch);
len=strlen(ch),ans=0,s=0,t=0;
FOR(i,0,len-1){
if(ch[i]=='(') ++s;
else if(ch[i]==')'&&s) --s,++ans;
if(ch[i]=='[') ++t;
else if(ch[i]==']'&&t) --t,++ans;
}
cout<<ans<<endl;
}
return 0;
}