Hướng dẫn giải của [VT Thiếu nhi] BÀI 21: TARR2
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
Cần tìm giá trị lớn nhất của ~S = A[i] \cdot X + A[j] \cdot Y~ với ~1 \le i \le j \le n~ (cho phép ~i = j~).
Lưu ý: đề cho phép ~i = j~ (cùng một phần tử dùng cho cả hai vị trí), nên khi duyệt phải tính cả trường hợp này.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 2000~
Thử mọi cặp ~(i, j)~ với ~i \le j~, lấy max. Giá trị tới ~2 \cdot 10^{18}~, vẫn nằm trong long long.
Sub 2: Prefix max — ~O(n)~
Duyệt ~j~ từ trái sang phải, giữ ~pm~ = max của ~A[i] \cdot X~ với ~i \le j~, rồi cập nhật đáp án bằng ~pm + A[j] \cdot Y~.
Chương trình hoàn chỉnh
main đọc ~n, X, Y~ và dãy số; nếu ~n \le 2000~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có 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;
long long X, Y;
vector<long long> A;
// Theo de: 1 <= i <= j <= n (cho phep i = j).
// Sub 1: thử mọi cặp i <= j, tính A[i]*X + A[j]*Y. O(n^2). Dùng khi n <= 2000.
void sub1() {
long long best = LLONG_MIN;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
best = max(best, A[i] * X + A[j] * Y);
cout << best << "\n";
}
// Sub 2: duyệt j, giữ max A[i]*X với i <= j (prefix max). O(n).
void sub2() {
long long best = LLONG_MIN, pm = LLONG_MIN;
for (int j = 0; j < n; j++) {
pm = max(pm, A[j] * X); // i <= j: tinh ca i = j
best = max(best, pm + A[j] * Y);
}
cout << best << "\n";
}
int main() {
freopen("TARR2.INP", "r", stdin);
freopen("TARR2.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> X >> Y;
A.resize(n);
for (int i = 0; i < n; i++) cin >> A[i];
if (n <= 2000) sub1();
else sub2();
return 0;
}
Bình luận