Lại là một bài toán cực đại hóa
Xem dạng PDF
Cho số nguyên ~N~ và mảng ~a_1, a_2, \ldots, a_n~. Điểm của một đoạn liên tiếp bằng tổng giá trị lớn nhất và giá trị bé nhất trong đoạn. Cắt mảng đã cho thành ~K~ đoạn liên tiếp không giao nhau, không rỗng sao cho tổng điểm của các đoạn là lớn nhất. Mỗi phần tử phải nằm trong chính xác một đoạn.
Input
Dòng đầu tiên gồm số nguyên ~N~ — Số lượng phần tử của mảng (~1 \leq N \leq 10^5, 1 \leq K \leq \min(N, 20)~).
Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_n~ – Giá trị của mảng (~0 \leq a_i \leq 10^9, \forall 1 \leq i \leq N~).
Output
Một số nguyên duy nhất là kết quả bài toán.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | 8 | ~K = \min(2, n)~ |
| 2 | 8 | ~a_1 \leq a_2 \leq \ldots \leq a_n~ hoặc ~a_1 \geq a_2 \geq \ldots \geq a_n~ |
| 3 | 18 | ~\max\limits_{i=1}^{N} a_i - \min\limits_{i=1}^{N} a_i \leq 10~ |
| 4 | 14 | ~N \leq 1000~ |
| 5 | 20 | ~N \leq 10000~ |
| 6 | 32 | Không có ràng buộc gì thêm |
Sample Input 1
5 3
3 5 2 3 4
Sample Output 1
22
Sample Input 2
3 2
10 6 2006
Sample Output 2
4028
Notes
Ở ví dụ 1, ta chia thành 3 đoạn ~[1, 1], [2, 2]~ và ~[3, 5]~. Kết quả của cách chia này là ~3 + 3 + 5 + 5 + 2 + 4 = 22.~
Ở ví dụ 2, ta chia thành 2 đoạn ~[1, 2]~ và ~[3, 3]~. Kết quả của cách chia này là ~10 + 6 + 2006 + 2006 = 4028~.
Bình luận