有一个括号序列，现在要计算一下它有多少非空子段是合法括号序列。
合法括号序列的定义是：
1.空序列是合法括号序列。
2.如果S是合法括号序列，那么(S)是合法括号序列。 3.如果A和B都是合法括号序列，那么AB是合法括号序列。
Input 多组测试数据。 第一行有一个整数T（1<=T<=1100000），表示测试数据的数量。 接下来T行，每一行都有一个括号序列，是一个由’(‘和’)'组成的非空串。 所有输入的括号序列的总长度不超过1100000。 Output 输出T行，每一行对应一个测试数据的答案。 Sample Input 5 ( () ()() (() (()) Sample Output 0 1 3 1 2
第一反应：这妥妥的dp。 然后想了半天状态转移都是错的。 定义状态dp[i]为以第i个括号结尾的合法括号子段的数量，那么dp[i]=dp[pos[i]-1]+1（pos[i]是和第i个括号匹配的左括号的位置） 然后答案就是把所有的dp值加起来。 原因：（自己找规律看看吧…QAQ） 再然后发现要用栈存储和右括号匹配的左括号？ 不要用memset，会T（别问我怎么知道的） 这道题的结果好像要用long long。 详见代码。
#include<cstdio> #include<stack> #include<cstring> #define maxn 1100005 using namespace std; int t,n,dp[maxn]; char s[maxn]; stack<int> sk; int main() { scanf("%d",&t); while(t--) { scanf("%s",s+1); n=strlen(s+1); while(!sk.empty()) sk.pop(); long long ans=0; for(int i=1;i<=n;i++) { dp[i]=0; if(s[i]==')') { if(!sk.empty()) { int l=sk.top();sk.pop(); dp[i]=dp[l-1]+1; ans+=1ll*dp[i]; } } else sk.push(i); } printf("%lld\n",ans); } }