MOWLAWN - Dọn dẹp khu vườn
Xem dạng PDF
Sắp đến lúc cuộc thi "Khu vườn đẹp nhất" diễn ra, nhưng nông dân John vẫn chưa chịu dọn dẹp khu vườn của mình. Anh quyết định gọi đàn bò, gồm có ~N~ con ~(1 \le N \le 10^5)~ đến trợ giúp. Ngay lập tức, đàn bò đã đến và xếp thành 1 hàng ngang. Từ trái qua phải, con bò thứ ~i~ sẽ có giá trị hiệu quả là ~E_i (0 \le E_i \le 10^9~).
Rất không may cho John, mặc dù đàn bò của anh có thể dọn dẹp khu vườn rất hiệu quả, nhưng chúng cũng là những con bò phá hoại rất hiệu quả. Theo kinh nghiệm của mình, nếu John chọn nhiều hơn ~K (1 \le K \le N)~ con bò liên tiếp nhau trong hàng, thì thay vì dọn dẹp khu vườn, chúng sẽ tán gẫu, mở tiệc và làm khu vườn trở nên tan hoang. Do đó, bạn hãy giúp nông dân John chọn ra những con bò làm vườn, sao cho không quá ~K~ con bò liên tiếp nhau được chọn, và tổng độ hiệu quả của chúng là lớn nhất.
Input
- Dòng đầu tiên chứa ~N~ và ~K~ là số con bò John triệu tập, và số con bò liên tiếp tối đa mà John có thể chọn.
- ~N~ dòng sau, mỗi dòng chứa một số nguyên ~E_i~ là độ hiệu quả của con bò thứ ~i~.
Output
- Duy nhất 1 số nguyên là tổng độ hiệu quả trong cách lựa chọn tối ưu
Sample
Input #1
5 2
1
2
3
4
5
Output #1
12
Problem source: Kc97ble - Free Contest 17
Bình luận
mình xin phép chia sẻ cách giải bài này tại đây mong được mọi người ủng hộ ạ ^^