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
This comment is hidden due to too much negative feedback. Show it anyway.
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é.