[1] Correct Parenthesis Sequence Reformulation

The condition of being a correct parenthesis sequence can be reformulated as follows: the string has an equal number of (s and )s, and the minimum cumulative sum of the sequence obtained by replacing ( with \(+1\) and ) with \(-1\) is \(0\).

The reformulated conditions are easier to handle, so we use this version below.

[2] Solution

In the first operation, the number of (s does not change, so it is necessary to equalize the number of (s and )s by the second operation.

Let \(p\) be the number of (s and \(q\) be the number of )s, then the required number of second operations can be determined as \(\frac{|p-m|}{2}\).

From the reformulated conditions, it can be seen that if we are to replace ( with ), it is optimal to do it from right to left, and it is optimal to replace ) with ( from left to right.

Next, we consider the number of operations required to satisfy the condition that “the minimum cumulative sum of the sequence obtained by replacing ( with \(+1\) and ) with \(-1\) is \(0\)” by the first operation.

Similar to the discussion regarding the second operation, it suffices to consider only the operation of swapping the leftmost ) with the rightmost (. One operation increases the minimum cumulative sum by \(2\), so let \(l\) be the current minimum cumulative sum, then the required number of operations can be determined as \(\lceil\frac{-l}{2}\rceil\).

Note that two second operations can be substituted for the first operation, so we need to replace \(A\) with \(\min{(A,2B)}\) beforehand.

All the above processes can be performed in \(\mathrm{O}(N)\).

[3] Sample Implementation (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long a, b;
    cin >> n >> a >> b;
    a = min(a, 2 * b);
    string s;
    cin >> s;
    int p = count(s.begin(), s.end(), '(');
    int m = 2 * n - p;
    int d = p - m;
    long long res = 0;
    if(p > m) {
        for(int i = 2 * n - 1; i >= 0; --i) {
            if(s[i] == '(' and d) {
                d -= 2;
                s[i] = ')';
                res += b;
            }
        }
    } else {
        for(int i = 0; i < 2 * n; i++) {
            if(s[i] == ')' and d) {
                d += 2;
                s[i] = '(';
                res += b;
            }
        }
    }
    long long cum = 0, mn = 0;
    for(int i = 0; i < 2 * n; i++) {
        cum += (s[i] == '(' ? 1 : -1);
        mn = min(mn, cum);
    }
    res += (-mn + 1) / 2 * a;
    cout << res << endl;
}