Gọi ~dp[i]~ là tổng giá trị lớn nhất của dãy bông hoa kết thúc tại ~i~ và thỏa mãn điều kiện đề bài.

Khi đó, ta có: ~dp[i] = max(dp[j]) + a_i~ với ~j < i~ và ~h_j < h_i~.

Tuy nhiên, thử hết tất cả các giá trị của ~j~ sẽ dẫn đến chương trình có độ phức tạp ~\mathcal{O}(N^2)~, và dẫn đến TLE.

Chúng ta có thể sử dụng một cấu trúc dữ liệu để tìm giá trị của ~dp[i]~ nhanh hơn. Nhận thấy rằng khi đang tính ~dp[i]~, chúng ta đang tìm giá trị ~dp[j]~ lớn nhất mà ~h_j < h_i~ và cộng vào ~a_i~.

Nói cách khác, ta đang tìm ~dp[j]~ lớn nhất mà ~h_j \in [1, h_i - 1]~, giá trị này có thể được tìm bằng một cấu trúc dữ liệu như cây IT hay cây BIT trong ~\mathcal{O}(\log{}N)~.

Độ phức tạp: ~\mathcal{O}(N\log{}N)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;

int n;
long long bit[MAXN + 1];

void update(int i, long long x) {
    for ( ; i <= n; i += i & -i)
        bit[i] = max(bit[i], x);
}

long long query(int i) {
    long long ans = 0;
    for ( ; i > 0; i -= i & -i)
        ans = max(ans, bit[i]);
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    vector<int> h(n), a(n);
    for (int i = 0; i < n; ++i) cin >> h[i];
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) {
        update(h[i], query(h[i] - 1) + a[i]);
    }
    cout << query(n) << '\n';
}