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.

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

Please read the guidelines before commenting.


  • 0
    thiennhan37  commented on Nov. 14, 2024, 4:42 p.m. ← edit 4

    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


  • -4
    TVSown  commented on June 28, 2023, 4:32 a.m.

    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 ạ


    • -3
      nguyene2p  commented on June 30, 2023, 7:17 a.m.

      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.


      • -6
        HotStepBroz  commented on July 9, 2023, 8:06 a.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • -7
          TVSown  commented on July 14, 2023, 7:18 a.m.

          This comment is hidden due to too much negative feedback. Show it anyway.


          • -6
            2211khanhdh  commented on July 17, 2023, 4:29 p.m.

            This comment is hidden due to too much negative feedback. Show it anyway.


            • -6
              OrzSeaPosjtive  commented on July 18, 2023, 12:34 a.m.

              This comment is hidden due to too much negative feedback. Show it anyway.


              • -1
                vantien1526  commented on Aug. 24, 2023, 4:09 a.m.

                xét n = 1 rồi mình vẫn bị sai 1 test 1 ạ