鏈接

http://qscoj.cn/problem/11/

發布時間: 2017年2月21日 20:05?? 最后更新: 2017年2月21日 20:07?? 時間限制: 1000ms?? 內存限制: 128M

描述

喵哈哈村的括號序列和外界的括號序列實際上是一樣的。

眾所周知"()"這樣的，就是一個標準的括號序列；"()()()()"這樣也是括號序列；“((()))()”這樣也是一個合法的括號序列。但是"((("這樣，就不是一個合法的括號序列了。

現在沈寶寶非常好奇，給你一個字符串，請從中找出最長的合法括號序列出來。

不知道你能找到嗎？

輸入

第一行一個T，表示有T組數據。
接下來T行，每一行都是一個字符串。
保證字符串的長度小于100000。
而且字符串中保證只會出現"(",")"這兩種字符之一。
1<=T<=10

輸出

對于每一組測試數據，輸出最長的合法括號序列的長度。

樣例輸入1?
2 )((())))(()()) )( 樣例輸出1 6 0

題解
若為“（”，存入棧S，若遇到“）”，將“（”，“）“都標記為1，取出棧頂，若位置連續為1，用mx記錄括號組數。 #include<bits/stdc++.h> using namespace std; const int maxn = 100006; string s; int vis[maxn];void solve(){cin>>s;memset(vis,0,sizeof(vis));stack<int> S;for(int i=0;i<s.size();i++){if(s[i]=='(') S.push(i);else {if(S.size()==0)continue;vis[i]=1;vis[S.top()]=1;S.pop();}}int ans=0,mx=0;for(int i=0;i<s.size();i++){if(vis[i]==0) mx=0;else mx++;ans=max(ans,mx); }cout<<ans<<endl; }int main(){int n;cin>>n;while(n--){solve();} }

?

?

轉載于:https://www.cnblogs.com/EdSheeran/p/6522516.html

總結

以上是生活随笔為你收集整理的qscoj 11 喵哈哈村的括号序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。