51nod 1791 合法括号子段 括号匹配算法+dp计数

51nod./onlineJudge/questionCode.html#!problemId=1791

给定一串括号串，对于其中每个左括号‘(’最多只能找到一个与之相匹配的右括号‘)’。显然，在括号串固定的情况下，括号的匹配是固定不变的。

根据题意，空串为合法括号，“()”为合法括号串，若A为合法括号串则”(A)”为合法括号串。

那么我们可以先用括号匹配算法（利用栈）可以找出独立括号的配对情况。

比如下面的串“（）（（）））（（））（”，则独立括号的配对情况如下“（）”：，“（（））”：，“（）”：，“（（））”：，“（）”：。

假设括号匹配对用数组P[N]表示，初始化为-1，代表没有与之匹配的括号（右括号最终值是-1），P[i]表示在第P[i]个位置上的括号与第i个括号匹配。即若P[i]!=-1第i个位置上肯定是左括号，第P[i]个位置上肯定是右括号。

找出独立括号后，以每个括号为开头计算以该括号开头，能有多少对合法的括号序列。用ans[N]存储答案，Ans[i]表示以第i个括号开始能有多少种合法的序列。

可以用DP解决此问题公式如下：

   ans[i]={0ans[P[i]+1]+1P[i]=−1P[i]≠−1

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<assert.h>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<sstream>
#include<stack>
#include<queue>
#include<string>
#include<bitset>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;
#define me(s)  memset(s,0,sizeof(s))
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long llu;
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const double eps = 1e-15;
const int maxn = 1200000 + 10;
int pos[maxn];
int d[maxn];
int main()
{ios_base::sync_with_stdio(false);int T; string s;cin >> T;while (T--){cin >> s;int len = s.length(); stack<int> stc;for (int i = 0; i < len; i++) {pos[i] = -1; d[i] = 0;if (s[i] == '(') stc.push(i);else {if (!stc.empty()) {pos[stc.top()] = i;stc.pop();}}}ll ans = 0;for (int i = len - 1; i >= 0; i--) {if (pos[i] == -1) continue;d[i] = d[pos[i] + 1] + 1;ans += d[i];}cout << ans << endl;	}
}