Найти наименьшую стоимость перемещения лягушки на камень n.

@programist_dna · Регистрация: 02.12.2020

Студворк — интернет-сервис помощи студентам

Здравствуйте, опишите пожалуйста алгоритм решения нижепредставленной задачи или может даже напишите код, если вас не затруднит.

Лягушка
Имеются n камней, пронумерованных 1, 2, ..., n. Для каждого i (1 ≤ i ≤ n) высота i -го камня равна hi. Лягушка изначально находится на камне 1. Она повторяет следующее действие некоторое количество раз для достижения камня n: если лягушка находится на камне i, то она может прыгнуть или на камень i + 1 или на камень i + 2. Стоимость перемещения с i-го на j-ый камень равна |hi − hj|.

Найдите наименьшую стоимость перемещения лягушки на камень n.

Входные данные
Первая строка содержит количество камней n (2 ≤ n ≤ 105). Вторая строка содержит целые числа h1, h2, ..., hn (1 ≤ hi ≤ 104).

Выходные данные
Выведите наименьшую стоимость перемещения лягушки на камень n.

Байт · 02.12.2020, 21:30

Имхо, хорошая задача на динамическое программирование!
А 105 это наверное 10⁵? Ты хоть пиши 10^5 что ли

@programist_dna · 02.12.2020, 22:05 **[ТС]**

Байт, да 105 это 10^5, прошу прощения.

@nalbe666 · 02.12.2020, 22:22

programist_dna, заведите массив с весами k[1, n], где каждое значение k[i] - это минимум из (k[i - 2] + |h[i] − h[i-2]|, k[i - 1] + |h[i] − h[i-1]|). Ответом будет значение k[n].
Даже массив не нужен, просто надо помнить два предыдущих значения.

Байт · 02.12.2020, 23:43

nalbe666, а чему равны k[1] и k[2] ?

@nalbe666 · 03.12.2020, 00:02

Байт, k[1] = 0, k[2] = |h[1] - h[2]|, естественно.

@programist_dna · 03.12.2020, 10:03 **[ТС]**

nalbe666, спасибо за помощь.

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача №1: при указании работ (справочник РаботыПоРемонтуСпецтехники),. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@programist_dna 0 / 0 / 0 Регистрация: 02.12.2020 Сообщений: 3

	Найти наименьшую стоимость перемещения лягушки на камень n. 02.12.2020, 17:56. Показов 3685. Ответов 6 Метки c++, дин. программирование (Все метки) Здравствуйте, опишите пожалуйста алгоритм решения нижепредставленной задачи или может даже напишите код, если вас не затруднит. Лягушка Имеются n камней, пронумерованных 1, 2, ..., n. Для каждого i (1 ≤ i ≤ n) высота i -го камня равна hi. Лягушка изначально находится на камне 1. Она повторяет следующее действие некоторое количество раз для достижения камня n: если лягушка находится на камне i, то она может прыгнуть или на камень i + 1 или на камень i + 2. Стоимость перемещения с i-го на j-ый камень равна \|hi − hj\|. Найдите наименьшую стоимость перемещения лягушки на камень n. Входные данные Первая строка содержит количество камней n (2 ≤ n ≤ 105). Вторая строка содержит целые числа h1, h2, ..., hn (1 ≤ hi ≤ 104). Выходные данные Выведите наименьшую стоимость перемещения лягушки на камень n. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	02.12.2020, 21:30
	Имхо, хорошая задача на динамическое программирование! А 105 это наверное 10⁵? Ты хоть пиши 10^5 что ли 0

@programist_dna 0 / 0 / 0 Регистрация: 02.12.2020 Сообщений: 3
	02.12.2020, 22:05 [ТС]
	Байт, да 105 это 10^5, прошу прощения. 0

@nalbe666 863 / 513 / 215 Регистрация: 19.01.2019 Сообщений: 1,216
	02.12.2020, 22:22
	Сообщение было отмечено programist_dna как решение Решение programist_dna, заведите массив с весами k[1, n], где каждое значение k[i] - это минимум из (k[i - 2] + \|h[i] − h[i-2]\|, k[i - 1] + \|h[i] − h[i-1]\|). Ответом будет значение k[n]. Даже массив не нужен, просто надо помнить два предыдущих значения. 2

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	02.12.2020, 23:43
	nalbe666, а чему равны k[1] и k[2] ? 0

@nalbe666 863 / 513 / 215 Регистрация: 19.01.2019 Сообщений: 1,216
	03.12.2020, 00:02
	Байт, k[1] = 0, k[2] = \|h[1] - h[2]\|, естественно. 2

@programist_dna 0 / 0 / 0 Регистрация: 02.12.2020 Сообщений: 3
	03.12.2020, 10:03 [ТС]
	nalbe666, спасибо за помощь. 0

Найти наименьшую стоимость перемещения лягушки на камень n.

Решение