Làm dãy tăng nghiêm ngặt
Đề bài
Mô tả
Cho dãy số nguyên .
Mỗi thao tác, bạn chọn một chỉ số bất kỳ rồi tăng hoặc giảm đi . Mỗi thao tác tốn chi phí .
Hãy tìm tổng chi phí nhỏ nhất để dãy trở thành tăng nghiêm ngặt, nghĩa là .
Các phần tử sau khi biến đổi là số nguyên tuỳ ý: chúng được phép âm và được phép vượt ra ngoài khoảng giá trị ban đầu.
Dữ liệu vào
- Dòng đầu chứa số nguyên .
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 2 1 5 11 5 9 11 |
9 | Đổi dãy thành 0 1 5 6 7 9 11, chi phí . |
| 3 10 1 1 |
11 | Đổi dãy thành 0 1 2, chi phí . Nếu chỉ được phép nâng lên thì phải dùng 10 11 12 với chi phí , nên việc hạ phần tử đầu là bắt buộc. |
| 5 5 4 3 2 1 |
12 | Đổi dãy thành 1 2 3 4 5, chi phí . |
Bình luận