合法子括号串数

autofish · 2020-09-07 20:01:43 · 个人记录

例子：

()(())

i=2时，答案+1，而i=5时，由于i=3在中间隔开，1~5不是一个合法的括号串，所以答案+1=2；

而i=6时1~2，3~6能合成一个匹配的序列，所以对答案+2 所以这个总括号串有4个合法子括号串

我们发现，一个后括号如果能匹配一个前括号，假设这个前括号的前 1位同样有一个已经匹配了的后括号，那么我们势必可以把当前的匹配和之前的匹配序列合并，当前的这个后括号的贡献值，其实就等于前面那个后括号的贡献值+1

#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn = 5e5+10;
char kh[maxn];//括号数组 
int dp[maxn];//dp表示前i个括号后，以第i个括号为结尾的合法子串个数；
int sum[maxn];//sum表示前i个括号总共有多少个合法子串 
int n;
int sta[maxn],top;//栈 
int main(){
    IOS;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i){
        cin >> kh[i]; 
    }
    for(int i = 1 ; i <= n ; ++i){
        if(kh[i]=='('){
            sta[++top] = i;
        }
        else{
            if(top==0) continue;
            int t = sta[top--];
            dp[i] = dp[t-1]+1; 
        }
        sum[i] = sum[i-1]+dp[i];
    }
    cout << sum[n];
    return 0;
}