Ý tưởng giải bài

Bài toán: Cho dãy kí tự ngoặc s[1..n] cùng độ đẹp tương ứng c[1..n], tìm đoạn con liên tiếp sao cho tạo được chuỗi ngoặc đúng và tổng độ đẹp lớn nhất.

1. Prefix sum

• Tính mảng prefix[i] = c[1] + c[2] + ... + c[i] để có thể lấy nhanh tổng độ đẹp của bất kỳ đoạn [l..r] chỉ với:

  ll segment = prefix[r] - prefix[l-1];
  

2. Stack theo dõi ngoặc mở chưa khớp

• Dùng vector<int> st hoặc stack<int> để lưu chỉ số của các ngoặc mở.
• Đặt một phần tử sentinel (ví dụ 0 hoặc -1) vào đầu để dễ tính khoảng cách.
• Khi gặp kí tự:
  • Mở ('(', '[', '{'): đẩy chỉ số vào stack.
  • Đóng (')', ']', '}'):
    1. Kiểm tra đỉnh stack có phần tử ngoặc mở và khớp với ngoặc đóng hiện tại không.
    2. Nếu khớp, pop đỉnh để lấy j (vị trí ngoặc mở), sau đó tính độ đẹp của đoạn [j..i].
    3. Nếu không khớp hoặc stack rỗng, gọi là vị trí "mismatch" và xóa sạch stack, rồi đẩy vị trí hiện tại làm sentinel mới.

3. Mảng DP để nối các đoạn đúng liên tiếp

• Định nghĩa dp[i] = tổng độ đẹp lớn nhất của một đoạn ngoặc đúng kết thúc tại chỉ số i.
• Khi vừa pop được cặp khớp (j, i), đoạn con [j..i] có độ đẹp là

  ll curr = prefix[i] - prefix[j-1];

• Nếu ngay trước j có một đoạn hợp lệ kết thúc tại j-1 (dp[j-1] > 0), ta cộng vào:

  if (dp[j-1] > 0)
      curr += dp[j-1];
  dp[i] = curr;
  

• Mỗi lần cập nhật dp[i], so sánh để tìm kết quả cuối cùng:

  ans = max(ans, dp[i]);
  

4. Kết quả

• Vì cho phép chọn dãy rỗng (tổng độ đẹp = 0), nên cuối cùng in:

  cout << max(ans, 0LL) << "\n";
  

Độ phức tạp: O(n) thời gian, O(n) bộ nhớ, đáp ứng được (n \le 10^5).

5. Code mẫu

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

static inline bool isMatching(char open, char close) {
    return (open == '(' && close == ')')
        || (open == '[' && close == ']')
        || (open == '{' && close == '}');
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<ll> beauty(n + 1), prefix(n + 1, 0), dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> beauty[i];
        prefix[i] = prefix[i - 1] + beauty[i];
    }

    vector<int> st;
    st.reserve(n);
    ll ans = 0;

    for (int i = 1; i <= n; ++i) {
        char ch = s[i - 1];
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push_back(i);
        } else {
            if (!st.empty()) {
                int j = st.back();
                char open = s[j - 1];
                if (isMatching(open, ch)) {
                    st.pop_back();
                    ll curr = prefix[i] - prefix[j - 1];
                    if (j > 1 && dp[j - 1] > 0)
                        curr += dp[j - 1];
                    dp[i] = curr;
                    ans = max(ans, curr);
                } else {
                    st.clear();
                }
            } else {
                // no matching open, reset
                st.clear();
            }
        }
    }

    cout << max(ans, 0LL) << '\n';
    return 0;
}