Hướng dẫn giải của [VTT Q4 Contest 13] Bài 3: Biến đổi dãy số [SUMMAX]
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
Đổi dấu một đoạn có tổng ~s~ làm tổng cả mảng đổi từ ~T~ thành ~T - 2s~. Vậy muốn tổng lớn nhất thì chọn đoạn có tổng nhỏ nhất (hoặc không làm gì, ứng với ~s = 0~).
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Duyệt mọi đoạn ~[l, r]~, cộng dồn tổng đoạn, cập nhật đáp án ~T - 2s~. Nếu chỉ nộp sub này: đúng 13/20 test.
Sub 2: Kadane — ~O(n)~
Tìm đoạn con có tổng nhỏ nhất bằng thuật toán Kadane (phiên bản min): ~cur = \min(cur + a_i, a_i)~. Khởi tạo kết quả nhỏ nhất bằng 0 để cho phép không thao tác. Đáp án ~T - 2 \cdot mn~, dùng long long vì tổng tới ~2 \cdot 10^{14}~. 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 \le 1000~ 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 a[200005];
// Sub 1: thử mọi đoạn [l,r] — O(n^2), dùng khi n <= 1000
void sub1() {
long long total = 0;
for (int i = 0; i < n; i++) total += a[i];
long long best = total;
for (int l = 0; l < n; l++) {
long long s = 0;
for (int r = l; r < n; r++) {
s += a[r];
best = max(best, total - 2 * s);
}
}
cout << best << "\n";
}
// Sub 2: đổi dấu đoạn có tổng s làm tổng mới = total - 2s,
// nên cần đoạn có tổng NHỎ nhất (Kadane) — O(n)
void sub2() {
long long total = 0;
for (int i = 0; i < n; i++) total += a[i];
long long cur = 0, mn = 0; // mn = 0 ứng với không làm gì
for (int i = 0; i < n; i++) {
cur = min(cur + a[i], a[i]);
mn = min(mn, cur);
}
cout << total - 2 * mn << "\n";
}
int main() {
freopen("SUMMAX.INP", "r", stdin);
freopen("SUMMAX.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
}
Bình luận