题目

原题链接：A. The Monster

题意

给出一个字符串，问其中有多少个回文括号序列。
参考了其他作者的代码。记录左右括号的配对情况，先把‘？’当成右括号，当左括号不够时用‘？’充当左括号。左右相同的情况下计数+1。

代码

#include<bits/stdc++.h>
using namespace std;
int vis[5000][5000]= {0};
int main() {
    string s;
    cin>>s;
    int l=s.size(),ans=0;
    for(int i=0; i<l; i++) {
        int tmp=0,t=0;
        for(int j=i; j<l; j++) {
            if(s[j]=='(') tmp++;
            else if(s[j]==')') tmp--;
            else tmp--,t++;
            if(tmp<0) {
                if(t>0) t--,tmp=1;
                else break;
            }
            if(tmp==0) ans++;
        }
    }
    cout<<ans;
    return 0;
}