Hướng dẫn giải của Biến đổi dãy số (THCS KS3 VTT)
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
Doi dau mot doan lam tong doi -2*s, nen dap an = tong + max(0, -2 * tong doan con nho nhat).
Sub 1: Vet can, ~N \le 1000~ ~O(N^2)~
Thu moi doan [l..r]. Chay rieng: dung 13/20 test.
Sub 2: Kadane, ~N \le 2 \cdot 10^5~ ~O(N)~
Tim tong doan con nho nhat bang Kadane. Chay rieng: dung 20/20 test.
Chương trình hoàn chỉnh
Neu N <= 1000 dung sub 1, nguoc lai dung sub 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<ll> a;
// Sub 1: vet can O(N^2), dung khi N <= 1000: thu moi doan [l..r], doi dau doan nay lam tong doi -2*s
void sub1() {
ll total = 0;
for (ll x : a) total += x;
ll best = 0; // khong doi dau gi cung duoc (loi ich >= 0)
for (int l = 0; l < n; l++) {
ll s = 0;
for (int r = l; r < n; r++) {
s += a[r];
best = max(best, -2 * s);
}
}
cout << total + best << "\n";
}
// Sub 2: Kadane O(N): tim doan con co tong nho nhat, khi do loi ich = -2 * tong do
void sub2() {
ll total = 0;
for (ll x : a) total += x;
ll cur = 0, mn = 0;
for (ll x : a) {
cur = min(x, cur + x); // tong nho nhat cua doan ket thuc tai x
mn = min(mn, cur);
}
cout << total - 2 * mn << "\n";
}
int main() {
freopen("SUMMAX.INP", "r", stdin);
freopen("SUMMAX.OUT", "w", stdout);
cin >> n;
a.resize(n);
for (auto& x : a) cin >> x;
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận