51nod 1478 括号序列最长合法子段

还是套路题，左括号就压栈，右括号就取出一个左括号配对，长度就是前面左括号前面已经合法的最长长度+这一部分左右括号，即拼起来，dp[i]存一下i前面的最长合法子段长度

坑点是不存在合法子串要输出0 1，最开始没看到。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
#define LL long long
#define debug(x) cout << "[" << x << "]" << endl
using namespace std;

const int mx = 1e6+10;
char a[mx];
int dp[mx];
stack<int> s;

int main(){
    int ans = 0, num = 1;
    scanf("%s", a+1);
    int len = strlen(a+1);
    for (int i = 1; i <= len; i++){
        if (a[i] == '(') s.push(i);
        else if (!s.empty()){
            int t = s.top(); s.pop();
            dp[i] = dp[t-1]+i-t+1;
            if (ans == dp[i]) num++;
            else if (ans < dp[i]) ans = dp[i], num = 1;
        }
    }
    printf("%d %d
", ans, num);
    return 0;
}