Educational Segment Tree Contest - ITMED

Xem dạng PDF
Gửi bài giải
Điểm: 0,15
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài:
Educational Segment Tree Contest - Anh Long
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trò chơi này thật đơn giản: Bạn có ~n~ hộp được đánh số từ 1 đến ~n~ và một số ~k~. Trong mỗi hộp có một tấm séc ghi số ~a_i~. Nếu bạn chọn hộp ~i~ và ~a_i\ge0~ thì bạn sẽ nhận được ~a_i~ đồng còn ~a_i \le 0~ thì bạn sẽ phải "lộp" cho chương trình ~|a_i|~ đồng.

Bằng khả năng "see the future" khủng của mình, bạn đã biết được con số ghi trên tấm séc trong mỗi hộp. Nhiệm vụ của bạn bây giờ chỉ còn là kiếm nhiều tiền nhất. Nhưng, trò chơi này có 2 điều luật như sau:

  • Ví dụ bạn chọn hộp thứ ~i~, thì hộp tiếp theo bạn chọn phải có chỉ số ~\le i+k~. Với hộp đầu tiên thì bạn có thể chọn tùy ý.
  • Bạn chỉ được chọn các hộp từ trái qua phải. Nói cách khác, nếu bạn chọn hộp thứ ~i~ thì hộp tiếp theo bạn chọn phải có số thứ tự ~>i~.

Bạn hãy tìm cách chơi để đem về nhà được nhiều tiền nhất nhé.

Input

  • Dòng đầu tiên là 2 số ~n~ và ~k~ (~1\le n,k \le 10^5~)
  • Dòng thứ 2 là ~n~ số nguyên là số ghi trên tấm séc trong mỗi hộp (~|a_i|\le 10^9~)

Output

1 số duy nhất là số tiền nhiều nhất bạn có thể kiếm được

Sample Input

5 2
-1 -2 3 -4 5

Sample Output

8

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    HeroMinhSteve  đã bình luận lúc 28, Tháng 2, 2025, 16:52

    Bài này có tính cả trường hợp ko chọn hộp nào nữa thì phải:) 2 test cuối quên tính cả trường hợp ko lấy xong tạch.

    DP

    Gọi dp[i] là số tiền nhận được lớn nhất nếu chọn hộp quà i là hộp quà bắt đầu.

    Khi chọn i là ô đầu tiên, đương nhiên là ta sẽ nhận được a[i] đồng, và sẽ chọn được thêm hộp quà trong khoảng từ i+1 -> i+k.

    Từ đó có thể thấy dp[i]= a[i] + hộp quà nào đó. vì a[i] có thể tính luôn nên dp[i] sẽ lớn nhất khi số hộp quà đó lớn nhất.

    => dp[i]= a[i]+ max(dp[j],0) với i<j<=i+k. (phải là dp[j] vì có thể sau lần chọn đó có thể chọn hộp tiếp theo)

    Duyệt ngược + dùng Segment tree Max để tính nhanh max(dp[j]) bằng cách tính được dp[i] thì update thẳng vào segment tree

    https://ideone.com/JqBFrR


  • -2
    ngocthamantinhoaian  đã bình luận lúc 3, Tháng 2, 2025, 9:45

    https://ideone.com/6ipgHl


  • 1
    nguyenvananh23052008  đã bình luận lúc 18, Tháng 1, 2025, 6:40

    2 test cuối là sao vậy mà e thử mọi cách k ac


    • 0
      huygd  đã bình luận lúc 27, Tháng 3, 2025, 13:48 ← chỉnh sửa

      2 test cuối là không chọn hộp nào =))


  • -6
    DuaConBienCa_longhai  đã bình luận lúc 14, Tháng 9, 2024, 1:52 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -6
    playerno1  đã bình luận lúc 12, Tháng 8, 2024, 3:19 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 58
    ntkiet  đã bình luận lúc 18, Tháng 4, 2023, 13:53 ← sửa 2

    Bài toán có thể được giải bằng phương pháp QHĐ kết hợp với Segment Tree.

    Gọi f[i] là số tiền bự nhất có thể kiếm được khi xét đến ai, với cái hộp cuối cùng được chọn là a[i]. Công thức quy hoạch động như sau: f[i] = max(a[j] + a[i]) (j : i - k -> i - 1)

    Có thể dùng Segment tree để xác định số tiền bự nhất xét đến trước đó (với k lớn, chạy hai vòng for chắc chắn bị TLE nên có thể kết hợp thêm Segment Tree) khi xét đến các hộp có giá trị từ i - k đến i - 1. Sau khi tìm ra số tiền bự nhất trước đó trong đoạn i - k, có thể tính ngay f[i], sau đó cập nhật f[i] vào Segment tree. (mmb)


  • -44
    phuoc2902  đã bình luận lúc 24, Tháng 12, 2021, 9:06

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -19
      dinhngoctuyen4125  đã bình luận lúc 19, Tháng 5, 2022, 17:09

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -55
    thanhchauns2  đã bình luận lúc 24, Tháng 12, 2021, 5:05

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 172
    YugiHackerKhongCopCode  đã bình luận lúc 20, Tháng 12, 2021, 12:22

    Cmt này spoil thuật!

    Có thể không cần dùng IT

    Quy hoạch động

    Gọi f[i] là số tiền nhiều nhất có thể kiếm được khi chọn hộp thứ i là hộp bắt đầu

    => f[i] = max(f[j], 0) + a[i] với j từ i+1 đến i+k

    Cách tính max f[i+1] ... f[i+k]:

    C1: Dùng IT

    Code lấy max của đoạn như bình thường. (O(NlogN))

    C2: Dùng deque

    Tìm max trên đoạn tịnh tiến độ dài k, vừa cập nhật mảng f, vừa cập nhật deque. (O(N))


    • -363
      nam80022052  đã bình luận lúc 2, Tháng 1, 2023, 13:09

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -27
        eya  đã bình luận lúc 28, Tháng 12, 2023, 11:10

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


        • -18
          HaoNoChetChua  đã bình luận lúc 9, Tháng 1, 2024, 13:41

          Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


          • -10
            playerno1  đã bình luận lúc 12, Tháng 8, 2024, 3:20

            Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


        • -26
          quangklpx  đã bình luận lúc 3, Tháng 1, 2024, 8:14

          Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.