Hướng dẫn giải của [VTT Q4 Contest 10] Bài 3: Dãy dài nhất [MAXSEQ]
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.
Hướng dẫn giải
Cần ghép một đoạn không giảm kết thúc tại ~a_j~ với một đoạn không giảm bắt đầu tại ~b_l~ sao cho ~a_j \le b_l~. Độ dài tối ưu của mỗi nửa độc lập nhau: đoạn dài nhất kết thúc tại ~a_j~ là ~la_j~, đoạn dài nhất bắt đầu tại ~b_l~ là ~rb_l~. Test thật cho thấy các dãy không nhất thiết đã sắp xếp (như ví dụ), nên ta tính ~la~, ~rb~ theo đúng nghĩa đoạn liên tiếp không giảm.
Sub 1: Vét cạn — ~O(nm)~, dùng khi ~n, m \le 1000~
Thử mọi cặp ~(j, l)~ với ~a_j \le b_l~, lấy max của ~la_j + rb_l~. Nếu chỉ nộp sub này: đúng 13/20 test (các test lớn bị quá thời gian).
Sub 2: Sắp xếp và chặt nhị phân — ~O(n \log n + m \log n)~
Sắp xếp các ~a_j~ theo giá trị, tính max tiền tố của ~la~. Với mỗi ~l~, chặt nhị phân xem có bao nhiêu ~a~ không vượt quá ~b_l~ rồi lấy max tiền tố tương ứng cộng ~rb_l~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc dữ liệu, ~n, m \le 1000~ gọi sub1, ngược lại sub2. Khi đi thi nên viết như vậy: sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long a[100005], b[100005];
int la[100005]; // la[j]: độ dài đoạn không giảm dài nhất kết thúc tại a[j]
int rb[100005]; // rb[l]: độ dài đoạn không giảm dài nhất bắt đầu tại b[l]
void prepare() {
for (int j = 1; j <= n; j++) la[j] = (j > 1 && a[j - 1] <= a[j]) ? la[j - 1] + 1 : 1;
for (int l = m; l >= 1; l--) rb[l] = (l < m && b[l] <= b[l + 1]) ? rb[l + 1] + 1 : 1;
}
// Sub 1: thử mọi cặp (j, l) với a[j] <= b[l] — dùng khi n, m <= 1000
void sub1() {
prepare();
int ans = 0;
for (int j = 1; j <= n; j++)
for (int l = 1; l <= m; l++)
if (a[j] <= b[l]) ans = max(ans, la[j] + rb[l]);
cout << ans << "\n";
}
// Sub 2: sắp xếp các a[j] theo giá trị, lấy max tiền tố của la, với mỗi l chặt nhị phân
void sub2() {
prepare();
vector<pair<long long, int>> v;
for (int j = 1; j <= n; j++) v.push_back({a[j], la[j]});
sort(v.begin(), v.end());
vector<int> pm(n);
for (int i = 0; i < n; i++) pm[i] = max(v[i].second, i ? pm[i - 1] : 0);
int ans = 0;
for (int l = 1; l <= m; l++) {
// số phần tử a có giá trị <= b[l]
int p = upper_bound(v.begin(), v.end(), make_pair(b[l], INT_MAX)) - v.begin();
if (p > 0) ans = max(ans, pm[p - 1] + rb[l]);
}
cout << ans << "\n";
}
int main() {
freopen("MAXSEQ.INP", "r", stdin);
freopen("MAXSEQ.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
if (n <= 1000 && m <= 1000) sub1();
else sub2();
}
Bình luận