trang chủ / đề bài / dhbb26_dx07_10_b

Dãy số

Đề bài

Mô tả

Cho dãy n số nguyên dương a1,a2,…,an. Với mỗi số ai (1≤i≤n) 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 ai 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 1: số nguyên dương n (1≤n≤105);
  • Dòng 2: n số nguyên dương a1,a2,…,an (1≤ai≤104, i=1…n).

Dữ liệu ra

Một số 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

  • 1≤n≤105;
  • 1≤ai≤104.

Subtasks

  • Subtask 1 (17 số điểm): n≤8, ai≤6.
  • Subtask 2 (17 số điểm): n<150.
  • Subtask 3 (17 số điểm): n<5000.
  • Subtask 4 (17 số điểm): n≤5000 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ố.
  • Subtask 5 (37 số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
5
2 6 4 3 2
5 Áp dụng 2 lần phép biến đổi "giảm a2 đi 1 đơn vị", 1 lần "tăng a4 lên 1 đơn vị", 2 lần "tăng a5 lên 1 đơn vị". Dãy thu được {2;4;4;4;4}.
5
2 6 6 7 7
0 Dãy đã không giảm.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0