Trò chơi với băng số

2017-08-02

algorithm

Bài gốc

Đề bài

Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương a_i, i = 1, 2, …, n. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô i₁, i₂, …, i_k. Khi đó điểm số mà người chơi đạt được sẽ là:

a_i₁ - a_i₂ + … + (-1)^(k-1)a_{i_k}

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Giới hạn:

1 ≤ n ≤ 10⁶
0 ≤ ai ≤ 10⁴

Định dạng test

Input:

Dòng đầu tiên chứa số nguyên dương n ( n ≤ 106 ) là số lượng ô của băng số.
Dòng thứ hai chứa n số nguyên dương a_i ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Output:

Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.

Ví dụ:

input:
7
4 9 2 4 1 3 7
---
output:
17

Thuật toán

DP: Tạo mảng dp[N][2] với ý nghĩa:

dp[i][0]: là số điểm tối đa nếu ta chọn một số lẻ các băng số trong đoạn [1, i] (kết thúc bởi việc trừ một băng số).
dp[i][1]: là số điểm tối đa nếu ta chọn một số chẵn các băng số trong đoạn [1, i] (kết thúc bởi việc cộng một băng số).

Lấy ví dụ tại phần tử thứ i, muốn tính dp[i][0], ta có 3 trường hợp sau đây:

Không chọn a_i vào băng số, dp[i][0] = dp[i-1][0].
Chọn duy nhất a_i vào băng số, dp[i][0] = -a[i].
Chọn a_i vào băng số như là phần tử tiếp theo của băng số đã chọn trước đó: dp[i][0] = dp[i-1][1] - a[i].

Như vậy dp[i][0] là giá trị lớn nhất trong 3 trường hợp trên, hoàn toàn tương tự cho dp[i][1].

Giá trị khởi tạo: dp[1][0] = 0, dp[1][1] = a[1].

Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N = 1e6 + 5;
int n;
ll f[N][2], a[N];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // input
    cin >> n;
    FOR(i,1,n) cin >> a[i];

    // dp init
    f[1][0] = 0;
    f[1][1] = a[1];

    // dp
    FOR(i,2,n) {
        f[i][0] = max(f[i-1][0], max(-a[i], f[i-1][1] - a[i]));
        f[i][1] = max(f[i-1][1], max(a[i], f[i-1][0] + a[i]));
    }
    cout << max(f[n][0], f[n][1]);

    return 0;
}

Độ phức tạp

O(N)

« Dãy con dài nhất có tổng lớn hơn bằng p Dãy con chung không liền kề dài nhất »