thêm một bài nữa, bài này là một ứng dụng của bài trên kia
Trích:
(Nguồn bài: Topcoder)
Cho một dãy các khẩu súng ngắn được xếp thành một dải hàng ngang. Có tất cả M loại súng và các khẩu súng cùng loại thì được xếp liên tiếp nhau. Ví dụ M=4
1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 4 4
Các loại súng được xếp theo thứ tự từ 1 đến M.
Ta có C[i] là số lượng súng loại i mà cửa hàng có và P[i] là mức phá hủy của loại súng i. Bạn cần trang bị N khẩu súng ngắn cho đội quân của mình và có một yêu cầu là N khẩu súng bạn chọn phải liên tiếp nhau. Hãy in ra tổng độ phá hủy lớn nhất có thể chọn được.
*input: nhập từ file guns.inp với dữ liệu được mô tả như sau:
_ Dòng đầu chứa 2 số M,N (M<=50, N<=1000000)
_ Dòng tiếp theo chứa M số là các số C[i]
_ Dòng tiếp theo chứa M số là các số P[i]
*output: xuất ra file guns.out với 1 dòng duy nhất là tổng độ phá hủy lớn nhất có thể chọn được.
Biết rằng N không vượt quá tổng số lượng súng.
VD:
*input
3 20
5 37 4
7 2 8
*output
65
*Giải thích: với bộ test trên ta sẽ có
_ 5 khẩu súng loại 1 được xếp đầu tiên (độ phá hủy mỗi khẩu là 7)
_ 37 khẩu súng loại 2 được xếp tiếp theo (độ phá hủy mỗi khẩu là 2)
_ 8 khẩu súng loại 3 được xếp cuối cùng (độ phá hủy mỗi khẩu là 8)
Cách chọn N khẩu liên tiếp tối ưu là chọn 5 khẩu loại 1 và 15 khẩu loại 2. Độ phá hủy là 5*7 + 15*2
*Lưu ý: vd test 1 1 1 2 2 3 3 3 3 ta có thể chọn 1 1 2 2 3 3 vẫn hợp lệ vì đó là các khẩu liên tiếp nhau.
|