VOI 09 Bài 1 - Trò chơi với băng số

View as PDF
Submit solution
Points: 0.08 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
Thi HSG Quốc gia 2009
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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, \dots, 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_{1}, i_{2}, \dots, i_{k}~. Khi đó điểm số mà người chơi đạt được sẽ là:

  • ~a_{i_1} - a_{i_2} + \dots + (-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.

Input

  • Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \leq 10^{6})~ là số lượng ô của băng số;
  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_{1}, a_{2}, \dots, a_{n}~ ~(a_{i} \leq 10^{4}, i = 1, 2, \dots, n)~ 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.

Giới hạn

60% số tests ứng với 60% số điểm của bài có ~1 \leq n \leq 20~.

Sample Input

7
4 9 2 4 1 3 7

Sample Output

17

Note

image

Comments

Please read the guidelines before commenting.


  • 4
    dangminh  commented on June 27, 2025, 1:27 p.m. ← edited

    Hint bài này:

    dùng quy hoạch động

    dp[i][0] là số điểm lớn nhất đến i và điểm tại đó là dương

    dp[i][1] tương tự nhưng điểm tại đó là âm

    duyệt i từ trái sang phải với mỗi dp[i] có 2 trạng thái là chọn hoặc ko chọn.

    tại dp[i][0] nếu chọn thì là dp[i][0] thì dp[i][1] + a[i]

    nếu ko chọn thì ta phải tìm đến trạng thái dương trước đó hay chính là dp[i][0]

    => dp[i][0] = max(dp[i-1][0],dp[i-1][1] + a[i])

    tại dp[i][1] tương tự có dp[i][1] = max(dp[i-1][0] - a[i],dp[i-1][1])

    vậy ct truy hồi là

    Với mỗi i từ 1->n

    dp[i][0] = max(dp[i-1][0],dp[i-1][1] + a[i])

    dp[i][1] = max(dp[i-1][0] - a[i],dp[i-1][1])


  • -5
    ijk  commented on Nov. 3, 2024, 3:33 p.m.

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


    • 0
      Trn115  commented on Nov. 4, 2024, 2:43 p.m.

      Hình như đề nói "theo thứ tự từ trái sang phải" mà


    • 0
      Trn115  commented on Nov. 4, 2024, 2:43 p.m.

      Hình như đề nói "theo thứ tự từ trái sang phải" mà