let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2009 LINEGAME - Trò chơi với băng số

solution.md

Gọi \(f_i\) là số điểm lớn nhất đạt được khi chọn trong dãy từ \(a_1\) đến \(a_i\) và số cuối cùng được chọn mang dấu dương. \(g_i\) tương tự nhưng số cuối cùng được chọn mang dấu âm.

Ta có công thức tính:

\[f_0 = a_0\\ g_0 = -a_0\\ f_i = max(f_{i-1}, a_i + g_{i-1}, a_i)\\ g_i = max(g_{i-1}, f_{i-1} - a_i, -a_i)\]

Kết quả là \(f_n\).

Ngoài ra ta có thể cải tiến để có độ phức tạp bộ nhớ O(1).

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
using namespace std;
#define LL long long

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    LL a, f, g;
    cin >> a;
    f = a;
    g = -a;
    for (int i=1; i<n; i++) {
        cin >> a;
        LL f1 = max(f, max(a + g, a));
        LL g1 = max(g, max(f - a, -a));
        f = f1;
        g = g1;
    }
    cout << f;
    return 0;
}
Comments