Dãy không giảm
Đề bài
Mô tả
Cho dãy số nguyên dương . Với mỗi số () ta có thể thực hiện "không, một hoặc nhiều lần" phép biến đổi "tăng hoặc giảm một đơn vị".
Yêu cầu: Hãy tính số phép biến đổi ít nhất để dãy đã cho thành dãy không giảm.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên dương .
- Dòng tiếp theo chứa số nguyên dương (, ).
Các số trên một dòng cách nhau bởi dấu cách.
Dữ liệu ra
Một số nguyên duy nhất là số phép biến đổi ít nhất để dãy đã cho thành dãy không giảm.
Ràng buộc
- ; .
- Có số test ứng với số điểm có , .
- Có số test khác ứng với số điểm có .
- Có số test khác ứng với số điểm có .
- Có số test khác ứng với số điểm có và đáp án bài toán tìm được chỉ bằng cách sử dụng phép biến đổi trên một phần tử của dãy số.
- Có số test khác ứng với số điểm có .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 6 4 3 2 |
5 | Áp dụng lần phép biến đổi "giảm đi đơn vị", lần "tăng lên đơn vị" và lần "tăng lên đơn vị". Dãy thu được là . |
| 5 2 6 6 7 7 |
0 | Dãy đã không giảm. |
Bình luận