Сделать массив неубывающим с помощью динамического программирования

Я столкнулся с этим вопросом в конкурсе по программированию, я думаю, что он может быть решен с помощью DP, но не могу придумать ни одного, поэтому, пожалуйста, помогите. Вот этот квест:

Существует n стопок монет, расположенных линейно, каждая из которых помечена от 1 до n. У вас также есть мешок монет с бесконечными монетами. Все монеты в стопках и мешке идентичны. Все, что вам нужно сделать, это сделать высоту монет неизменной.

Вы выбираете две стопки i и j и помещаете по одной монете в каждую стопку монет от стека i до стека j (включительно). Эта полная операция рассматривается как один ход. Вы должны минимизировать количество ходов, чтобы высота не уменьшалась.

No. of Test Cases < 50
1 <= n <= 10^5
0 <= hi <= 10^9

Входная спецификация:
Там будет ряд тестовых случаев. Читайте до EOF. Первая строка каждого теста будет содержать одно целое число n, вторая строка содержит n высот (h [i]) стеков.

Спецификация выхода:
Выведите единственное целое число, обозначающее количество ходов для каждого теста.

for eg: H={3,2,1}
answer is 2
step1: i=2, j=3, H = {3,3,2}
step2: i=3, j=3, H = {3,3,3}

0

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]