Условие задачи: Вам дан одномерный массив route длиной n, где каждая ячейка содержит число – стоимость прохождения через неё. Кузнечик начинает движение непосредственно перед первой клеткой и может прыгать на одну или две клетки вперёд. Необходимо пройти весь путь, прибыв в последнюю клетку, с минимальной суммарной стоимостью, а также вывести номера клеток, которые кузнечик посетит.

Формат входных данных: В первой строке задано число n (2 ≤ n ≤ 1,000,000). Во второй строке содержится n целых чисел, где 0 ≤ route[i] ≤ 100.

Формат выходных данных: В первой строке выведите минимальную суммарную стоимость прохождения. Во второй строке через пробел — номера клеток (целые числа от 1 до n), которые кузнечик посетит при оптимальном перемещении (например: 1 3 4 6).

Решение: Для решения задачи применяется метод динамического программирования. Создаётся одномерный массив dp, где dp[i] обозначает минимальную стоимость пути до клетки i. Одновременно формируется массив parent для восстановления маршрута, где parent[i] хранит индекс предыдущей клетки, через которую проходил оптимальный путь.

Начальные условия:

dp[0] = route[0]

dp[1] = route[1]

Для остальных клеток выбираем оптимальный переход – из клетки i - 1 или i - 2, одновременно обновляя индекс предка:

После заполнения массива dp значение dp[n-1] является минимальной суммарной стоимостью, а массив parent позволяет восстановить оптимальный маршрут.

Например, если дан следующий массив:

то после вычислений получится:

Восстановление пути: Начиная с клетки с индексом n - 1, последовательно следуйте по массиву parent, пока не достигнете начальной позиции (индекс 0 или 1). Полученный путь затем разворачивается для вывода правильной последовательности посещённых клеток.