Cho N ≤ 500 tòa nhà, với chiều cao là a[1..n] (a[i] ≤ 100). Được chọn nhiều nhất K ≤ N khối liên tiếp với chiều dài một khối không quá T ≤ N và các khối không phủ nhau. Phần hữu dụng của một khối từ i..j được tính bằng công thức : (j-i+1)*min(a[i..j]). Cần chọn thỏa điều kiện để tổng hữu dụng là max.
Dữ liệu vào:
- Dòng đầu tiên chứa 3 số nguyên dương N, K và T
- Dòng thứ hai chứa các số nguyên a1, a2, ..., aN.
Kết quả ra:
- Tổng hữu dụng là lớn nhất.
Giải thích ví dụ:
- Cần chọn 2 khối nhà, mỗi khối có tối đa 4 nhà liên tiếp: ta sẽ chọn 2 khối nhà với a[3..5] = (12, 11, 13) và a[7..10] = (8,6,6,20), khi đó tổng hữu dụng lớn nhất là:
3*min{12,11,13} + 4*min{8,6,6,20} = 57