Editorial for Atcoder Educational DP Contest Q - Flowers


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Mike4235

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';
}

Comments

Please read the guidelines before commenting.



  • -9
    AnhTranCPP   commented on Aug. 19, 2022, 7:29 a.m. edited

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 4
      jalsol   commented on Aug. 21, 2022, 8:20 p.m.

      chạy 1 for từ đầu đến cuối

      Bạn nên đọc thêm cách tính độ phức tạp thuật toán, rồi suy nghĩ xem cách "đơn giản" này chạy đủ nhanh không nhé.