Editorial for Bedao Grand Contest 13 - MAXSUM
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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; }
Comments
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.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
xét n = 1 rồi mình vẫn bị sai 1 test 1 ạ