Tối ưu hóa quy hoạch động bằng hàng đợi đơn điệu (Monotonic Queue DP)
Có một dãy gồm N bậc thang được đánh số từ 1 đến N. Tại mỗi bậc thang i có một chi phí phạt là Ci (có thể âm, bằng 0, hoặc dương).
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: dynamic-programming, deque.
Nội dung đề bài
Mô tả bài toán
Có một dãy gồm N bậc thang được đánh số từ 1 đến N. Tại mỗi bậc thang i có một chi phí phạt là Ci (có thể âm, bằng 0, hoặc dương).
Bạn bắt đầu tại bậc 1 với chi phí ban đầu là C1. Từ bậc i, bạn có thể nhảy tới bất kỳ bậc j nào thỏa mãn i < j ≤ i + K.
Yêu cầu: Hãy tìm chi phí nhỏ nhất để nhảy đến bậc N.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên N, K (2 ≤ N ≤ 1,000,000, 1 ≤ K ≤ N).
- Dòng thứ hai chứa N số nguyên C1, C2, …, CN (-109 ≤ Ci ≤ 109).
Dữ liệu ra
- In ra một số nguyên duy nhất là chi phí nhỏ nhất để đến được bậc N.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Các tham số truyền vào hàm/lớp solution hoặc dữ liệu đầu vào theo định dạng mô tả.
Output
- Kết quả trả về của hàm/lớp solution hoặc dữ liệu in ra màn hình theo đúng đặc tả.
Ràng buộc
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
Input:
5 2
1 -1 -2 4 -7
Output:
-7Output
Thành công / Đáp ứng đầy đủ ràng buộcGiải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.