Hướng dẫn giải của Bedao Grand Contest 13 - MAXSUM
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.
Nhận xét: luôn tồn tại một cách chọn ~2~ đoạn ~l, r~ không giao nhau và vẫn đạt được kết quả tối ưu.
Như vậy, ta có thể xây dựng các mảng ~minLeft~ và ~minRight~ ý nghĩa:
~minLeft[i]~ là cách chọn ~1~ đoạn ~l, r~ sao cho ~r \leq i~ và tổng các phần tử thuộc đoạn ~l, r~ là nhỏ nhất có thể.
~minRight[i]~ là cách chọn ~1~ đoạn ~l, r~ sao cho ~i \leq l~ và tổng các phần tử thuộc đoạn ~l, r~ là nhỏ nhất có thể.
Đáp án của bài toán là giá trị ~Sum(a) - 2 \times (minLeft[i] + minRight[i + 1])~ lớn nhất với mọi giá trị ~i~ mà ~1 \leq i < n~. Trong đó, ~Sum(a)~ là tổng các phần tử dãy ~a~.
Code mẫu
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define For(i, a, b) for (int i=a;i<=b;++i) #define Ford(i, a, b) for(int i=a;i>=b;--i) #define cerr cout #define deb(x) cerr << #x << ": " << x << endl #define deba(a, x, y) cerr << #a << ": ", printA(a, x, y) #define enter cerr << endl; template<class A> void printA(A a, int l, int r) { For(i, l, r) cerr << a[i] << " "; cerr << endl; } typedef long long ll; typedef pair<int, int> ii; typedef array<int, 3> arr; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; const int N = 2 * 1e5 + 5; void solve() { int n; cin >> n; vi a(n); for (int &x : a) cin >> x; if (n == 1) { cout << a[0]; return; } vll minLeft(n), minRight(n); ll s = 0, ma = 0; for (int i = 0; i < n; ++i) { s += a[i]; minLeft[i] = s - ma; if (i) minLeft[i] = min(minLeft[i], minLeft[i - 1]); ma = max(ma, s); } s = 0, ma = 0; for (int i = n - 1; i >= 0; --i) { s += a[i]; minRight[i] = s - ma; if (i < n - 1) minRight[i] = min(minRight[i], minRight[i + 1]); ma = max(ma, s); } s = 0; for (int x : a) s += x; ll ans = max({s, s - 2 * minRight[1], s - 2 * minLeft[n - 2]}); for (int i = 0; i < n - 1; ++i) { ans = max(ans, s - 2 * (minLeft[i] + minRight[i + 1])); } cout << ans; } int main() { // freopen(".inp","r",stdin); // freopen(".out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); solve(); return 0; }
Bình luận
bài này hơi ảo vd test: 2 2 -2 chỉ đổi -2 ra kq là 4 (tức làm 1 thao tác) thì mới ac được bài này mà không sai test 8. code mình: https://ideone.com/EjH9T1
cập nhật minLeft[i] bằng công thức: minLeft[i] = min(min(minLeft[i - 1], minLeft[i - 1] + a[i]), a[i]); cho e hỏi công thức này có đúng kh ạ
ct trên sai rồi nha, để tìm minleft, minright bạn làm giống như bài dãy con liên tiếp có tổng nhỏ nhất là đc.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
xét n = 1 rồi mình vẫn bị sai 1 test 1 ạ