Hướng dẫn giải của Atcoder Educational DP Contest Q - Flowers
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả: 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'; }
Bình luận
* Cho mình hỏi cách truy vết để ra dãy h được ko ạ*
b chỉ cần lưu cha của thằng max ấy b
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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é.