Reward

Xem dạng PDF
Gửi bài giải
Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

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


  • 1
    Rykrax   đã bình luận lúc 29, Tháng 5, 2024, 19:42

    Cmt này spoil thuật!

    Quy hoạch động

    Gọi dp[i][j] là tổng giá trị lớn nhất khi được chọn đến món quà thứ i và không quá j món quà liên tiếp

    Nhận xét: Khi chọn món quà thứ i sẽ có 2 TH:

    TH 1: Chọn món quà thứ i và ghép với món quà i-1 => Tạo thành 2 món quà liên tiếp

    CT: dp[i][j] = dp[i-1][1] + a[i]

    TH 2: Chọn món quà thứ i và món quà i-1 không được chọn => Tạo thành món quà đầu tiên liên tiếp

    CT: dp[i][j] = dp[i-2][2] + a[i]

    Lưu ý: giá trị món quà có thể âm

    Ngồi nháp ra sẽ dễ hiểu hơn nhé <3


  • 1
    Rykrax   đã bình luận lúc 7, Tháng 3, 2024, 6:17

    kẻ huỷ diệt dp 🐧