描述

有一个括号序列，现在要计算一下它有多少非空子段是合法括号序列。
合法括号序列的定义是：

1. 空序列是合法括号序列
2. 如果S是合法括号序列，那么(S)是合法括号序列
3. 如果A和B都是合法括号序列，那么AB是合法括号序列
   

题解

在括号串给定的情况下，括号的匹配是固定不变的，所以首先求出独立括号的配对情况。
pos[]表示括号匹配情况，初始化全为-1,表示没有与之匹配的括号。如果pos[i]不为-1，则原串的第i个位置必然是左括号，原串的第pos[i]个位置必然是右括号，且与第i个位置的左括号相对应。

ans[i]：以i开头的合法序列的个数，所以可以得到以下的状态转移方程：

最后的答案:

注意，由于此题数据量较大，不适合memset(pos,-1,sizeof(pos))对pos和ans进行初始化操作，会导致超时。

代码

#include <bits/stdc++.h>
using namespace std;
#define maxn 1100005
char ss[maxn];
int pos[maxn];
int ans[maxn];
stack<int>s;
int main()
{int T;scanf("%d",&T);while(T--){scanf("%s",ss);int len=strlen(ss);///清空栈while(!s.empty()) s.pop();///初始化操作for(int i=0; i<=len; i++){pos[i]=-1;ans[i]=0;}for(int i=0; i<len; i++){if(ss[i]=='('){s.push(i);continue;}if(s.empty())continue;int temp=s.top();s.pop();if(ss[temp]=='(')pos[temp]=i;}long long ANS=0;for(int i=len-1; i>=0; i--){if(pos[i]==-1)continue;ans[i]=ans[pos[i]+1]+1;ANS+=ans[i];}printf("%lld\n",ANS);}return 0;
}