Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость. Необходимо найти путь с минимальной стоимостью маршрута кузнечика из точки 0 в точку N. Формат ввода Первая строка содержит

Добавлена: 10.04.2026
Обновлена: 10.04.2026
Предмет: Другое
Автор: Кэмп

Условие:

Пусть кузнечик прыгает на одну или две точки вперед, а за прыжок в каждую точку необходимо заплатить определенную стоимость. Необходимо найти путь с минимальной стоимостью маршрута кузнечика из точки 0 в точку N.

Формат ввода
Первая строка содержит натуральное число 1 <= N <= 10^5 — номер точки, в которую кузнечику необходимо попасть. Вторая строка содержит N целых неотрицательных чисел, разделенных пробелами: i-ое значение означает цену прыжка в точку i для 1 <= i <= N. Все числа не превосходят 2^63 - 1.

Формат вывода
Программа должна вывести путь — номера точек, разделенные пробелами. Путь должен начинаться с точки 0 и заканчиваться точкой N. Гарантируется, что существует только один путь с минимальной стоимостью.

Решение:

Здравствуйте! Это классическая задача на динамическое программирование, где нам нужно найти не только минимальную стоимость, но и сам путь, который эту стоимость обеспечивает.

Давайте разберем задачу по шагам.

1. Дано

$N$ : Конечная точка назначения ( $1 \le N \le 10^5$ ).
$C_1, C_2, \ldots, C_N$ : Стоимость прыжка в точку $i$ . (В условии сказано "i-ое значение означает цену прыжка в точку $i$ для $1 \le i \le N$ ").
Кузнечик может прыгать на 1 или 2 точки вперед.
Начальная точка: 0.
Гарантируется, что существует только один путь с минимальной стоимостью.