合法括号子段 51Nod - 1791 （栈+dp）

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

合法括号序列的定义是：

1.空序列是合法括号序列。

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

思路 ：

这个题目样例非常多，如果你开的数组比较大，那么初始化的时间都很多，如果每次都memset全初始化，会对时间带来很大影响。

思路：就是括号配对，比较好的想法就是对于每个下标为i的左括号，如果它有右括号和它匹配，则pos[i]记录右括号位置，这样有什么用呢？可以这样想，如果我们倒序（与标记左括号有关）遍历一遍数组，在每个pos[i]存在的地方都能确定一个括号，那么这个括号就可以与前面已有的括号连续，dp【】记录每个位置前面连续括号的个数，那么，就会新产生dp+1个连续序列，例如 ： abcd，每个字母是个括号，a是刚找到的，就有a ， ab，abc，abcd四种，可以运算时维护结果。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>
#include <map>
#include <climits>
typedef long long ll;
using namespace std;int pos[1000005];
int dp[1000005];
char str[1000005];
int main()
{int t;scanf("%d",&t);getchar();while(t--){scanf("%s",str);stack <int> s;int i;for(i = 0; str[i]; i++){pos[i] = -1;if(str[i] == '('){s.push(i);continue;}if(s.empty()) continue;int p = s.top();s.pop();pos[p] = i;}ll ans = 0;for(i = i-1; i >= 0; i--){dp[i] = 0;int p = pos[i];if(p == -1) continue;dp[i] = dp[p+1] + 1;ans += dp[i];}printf("%I64d\n",ans);}return 0;
}