CFR 5 C. Longest Regular Bracket Sequence ( DP )

Problem - 5C - Codeforces
題意：
給括弧序列，求連續區間之最長的合法匹配長度，和其數量。
解法：
對於每個閉括弧，預處理和其配對的開括弧位置，並藉以更新對應的最遠合法左界。如果當前這個閉括弧能配對，那麼最遠合法的左界就是其對應的開括弧左邊一個閉括弧所對應的最遠合法左界。

string seq;

void init(){
    cin >> seq;
}

vi dpnear;
vi dpfar;

void preprocess(){
    dpnear = dpfar = vi( seq.size(), INF );
    stack< int > stk;
    for( int i = 0; i < seq.size(); ++i ){
        if( seq[ i ] == '(' )
            stk.push( i );
        else{
            if( stk.empty() )
                continue;
            dpnear[ i ] = stk.top(); stk.pop();
            dpfar[ i ] = min( dpnear[ i ], dpfar[ dpnear[ i ] - 1 ] );
        }
    }
}

void solve(){
    int maxlen = 0, cnt = 1;
    for( int i = 1; i < seq.size(); ++i ){
        if( upmax( maxlen, i - dpfar[ i ] + 1 ) )
            cnt = 1;
        else if( maxlen == i - dpfar[ i ] + 1 )
            ++cnt;
    }
    cout << maxlen << " " << cnt << endl;
}