Hướng dẫn giải của Tạo dãy
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Với mỗi ~k~, ~c_k~ là giá trị lớn nhất của ~a_i \cdot b_j~ với ~1 \le i \le j \le k~. Khi tăng ~k~, chỉ cần xét thêm các cặp có ~j = k~, nên ~c_k = \max(c_{k-1}, \max_{i \le k} a_i \cdot b_k)~.
Sub 1: Vét cạn ba vòng — ~O(n^3)~, dùng khi ~n < 100~
Với mỗi ~k~, thử mọi cặp ~i \le j \le k~. Nếu chỉ nộp sub này: đúng 5/10 test.
Sub 2: Cập nhật theo ~k~ — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi ~k~, duyệt ~i \le k~ để tìm ~\max a_i \cdot b_k~, rồi lấy ~\max(c_{k-1}, \cdot)~. Nếu chỉ nộp sub này: đúng 5/10 test.
Sub 3: Tiền tố lớn nhất — ~O(n)~
Giữ ~PM = \max_{i \le k} a_i~ (tiền tố lớn nhất), rồi ~c_k = \max(c_{k-1}, PM \cdot b_k)~. Tích có thể đến ~10^{18}~ nên dùng ~long long~. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
~main~ đọc ~N~ và hai dãy, nếu ~N < 100~ gọi sub1, nếu ~N \le 5000~ gọi sub2, ngược lại gọi sub3. Chương trình dùng nhập xuất nhanh.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[1000005], b[1000005]; // a[1..n], b[1..n] (n <= 10^6)
void printC(const vector<long long> &c) {
for (int k = 1; k <= n; k++) cout << c[k] << (k == n ? '\n' : ' ');
}
// Sub 1: O(n^3) (n < 100): voi moi k, thu moi cap (i, j) voi i <= j <= k
void sub1() {
vector<long long> c(n + 1, 0);
for (int k = 1; k <= n; k++) {
long long best = 0;
for (int i = 1; i <= k; i++)
for (int j = i; j <= k; j++)
best = max(best, a[i] * b[j]);
c[k] = best;
}
printC(c);
}
// Sub 2: O(n^2) (n <= 5000): c[k] = max(c[k-1], max_{i<=k} a[i] * b[k]).
// Cac cap (i, j) voi j < k da nam trong c[k-1]; chi can xet cap co j = k.
void sub2() {
vector<long long> c(n + 1, 0);
for (int k = 1; k <= n; k++) {
long long best = 0;
for (int i = 1; i <= k; i++) best = max(best, a[i] * b[k]);
c[k] = max(c[k - 1], best);
}
printC(c);
}
// Sub 3: O(n). Dung max tien to cua a: PM[k] = max a[1..k], c[k] = max(c[k-1], PM[k] * b[k]).
void sub3() {
vector<long long> c(n + 1, 0);
long long pm = 0;
for (int k = 1; k <= n; k++) {
pm = max(pm, a[k]);
c[k] = max(c[k - 1], pm * b[k]);
}
printC(c);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
if (n < 100) sub1();
else if (n <= 5000) sub2();
else sub3();
return 0;
}
Bình luận