51nod 1791 合法括号子段 （dp）

Description

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

合法括号序列的定义是：

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

Input

多组测试数据。

第一行有一个整数 T（1<=T<=1100000） ，表示测试数据的数量。

接下来 T 行，每一行都有一个括号序列，是一个由 ‘(‘ 和 ‘)’ 组成的非空串。

所有输入的括号序列的总长度不超过 1100000 。

Output

输出 T 行，每一行对应一个测试数据的答案。

Input 示例

5
(
()
()()
(()
(())

Output示例

0
1
3
1
2

思路

首先预处理出与每一个左括号所对应的右括号的位置， $cnt[i]=j$ 表示左括号 $i$ 所对应的右括号的位置为 $j$ 。

$dp[i]$ 代表 $i$ 右侧合法括号序列的数目。

则对于每一个左括号， $dp[i]=dp[cnt[i]+1]+1$ ，表示每一个左括号右侧合法括号序列数目 等于 与当前匹配的右括号右边相邻的左括号（如果有的话）序列数 加 当前这一对的数目。

AC 代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 1200000;
const int mod = 1e9+7;
typedef long long LL;
stack<int> sk;
int cnt[maxn];
LL ans[maxn];
char str[maxn];

void solve()
{
    while(!sk.empty())sk.pop();
    int len = strlen(str);
    for(int i=0; i<=len+1; i++)
    {
        ans[i] = 0;
        cnt[i] = -1;
    }
    for(int i=len-1; i>=0; i--)
    {
        if(str[i]==')')
            sk.push(i);
        else
        {
            if(sk.empty())
                continue;
            cnt[i] = sk.top();
            sk.pop();
        }
    }
    LL res = 0;
    for(int i=len-1; i>=0; i--)
    {
        if(cnt[i]!=-1)
        {
            ans[i] = ans[cnt[i]+1]+1;
            res += ans[i];
        }
    }
    printf("%lld\n",res);
}
int main()
{
    int T;
    scanf("%d%*c",&T);
    while(T--)
    {
        scanf("%s",str);
        solve();
    }
}