PKADKP - PKADKP
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Học dốt toán cũng là một cái tội
Ngày xửa ngày xưa cái thời mà đã có điện thoại di động ^^ ở 1 vương quốc nọ có một vị vua anh minh là adkp, vị vua có có một cô công chúa đẹp tuyệt trần vừa tròn 18 tuổi . Tương truyền rằng vị vua rất kén ăn nên quyết tâm kén 1 chàng rể nấu ăn giỏi . Nghe nói nhà vua kén rể các chàng trai từ khắp mọi miền đất nước đều háo hức, kéo đến cung điện tranh tài mong sao thoát được kiếp f.a , only_love97 cx không ngoại lệ .Vốn ái mộ công chúa từ rất lâu rồi và cũng rất may là nấu ăn khá giỏi nên only_love97 tự tin rằng mình sẽ lấy được công chúa làm vợ .Thật chớ trêu thay thử thách của vua khiến anh ta phải đau đầu vì nó cần kiến thức toán học nhiều hơn là nấu ăn(anh ta học rất dốt toán ) . Only_love97 rất hối hận nhưng điều đó là quá muộn rồi . Nhưng rồi thần may mắn đã đến với anh khi vua ban cho mỗi người 3 quyền trợ giúp : 50-50 , gọi điện thoại cho người thân và hỏi ý kiến khán giả trong cung điện . Only_love97 vui sướng rút điện thoại ra và gọi ngay về cho những coder VOJ để mong sự trợ giúp , anh ta hứa sẽ hậu tạ khi được làm phò mã ^^. Hãy giúp chàng trai tội nghiệp này nhé !
Thử thách mà vua đưa ra như sau:
Cho 1 thực đơn các món ăn được đánh số từ 1 tới n món ăn thứ i có chỉ số là i và thời gian nấu các món ăn được cho là a 1 …a n . Ở bước thứ i các đầu bếp chọn đoạn l i ..r i (l i ≤r i ≤n) với điều kiện là l i <>l i-1 , l i <>l i-2 ... l i <> l 1 ; ri<>r i-1... ,r i <>r 1 và (r i -l i +1≤k) rồi nấu tất cả các món ăn có thời gian nấu nhỏ nhất trong các món ăn chưa được nấu thuộc đoạn đó. Nhà vua muốn biết số bước nhỏ nhất mà đầu bếp phải thực hiện để nấu tất cả các món ăn.
Input
Dòng đầu 2 số N,k(1≤K≤N≤10 5 )
N dòng tiếp theo mỗi dòng gồm 1 số nguyên dương Ai (A i ≤10^9)
Output
1 dòng duy nhất là kết quả của bài toán
Example
Input:3 3
1
2
2
Output: 2
Giải thích chọn đoạn là [1;2] nấu món ăn mang chỉ số là 1
Chọn đoạn [2;3] nấu món ăn mang chỉ số 2,3
Bạn không thể chọn 2 đoạn là [1;3] và [2;3] ; hay [1,2] và[1;3]
- Người up: only_love97
- Nguồn bài: Ðào Phan Khải