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

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

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

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

Лягушка
Имеются 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, спасибо за помощь.

@programist_dna 0 / 0 / 0 Регистрация: 02.12.2020 Сообщений: 3
		1
	Найти наименьшую стоимость перемещения лягушки на камень n. 02.12.2020, 17:56. Показов 3277. Ответов 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

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

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

@nalbe666 817 / 504 / 211 Регистрация: 19.01.2019 Сообщений: 1,196
	02.12.2020, 22:22	4
	Сообщение было отмечено 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

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

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

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

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

Решение