Я столкнулся с этим вопросом в конкурсе по программированию, я думаю, что он может быть решен с помощью 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}
Задача ещё не решена.
Других решений пока нет …