Codeforces Round 371 (Div. 1) |
---|
Закончено |
Сова Соня не придумала легенду к этой задаче и просто написала вам формальное условие.
Дан массив длины n, содержащий целые положительные числа. За одну операцию можно увеличить или уменьшить на 1 любое число в массиве. Требуется сделать массив строго возрастающим за минимальное количество операций. Числа можно изменять произвольным образом, в том числе они могут стать отрицательными или равными 0.
Первая строка входных данных содержит единственное число n (1 ≤ n ≤ 3000) — длину массива.
Следующая строка содержит n целых чисел ai (1 ≤ ai ≤ 109).
Выведите одно число — минимальное количество операций, которое потребуется применить, чтобы массив стал строго возрастающим.
7
2 1 5 11 5 9 11
9
5
5 4 3 2 1
12
В первом примере массив после изменений будет выглядеть так:
2 3 5 6 7 9 11
|2 - 2| + |1 - 3| + |5 - 5| + |11 - 6| + |5 - 7| + |9 - 9| + |11 - 11| = 9
Во второй примере так:
1 2 3 4 5
|5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12
Название |
---|