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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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