DjangoBB LoFi version

Начало » Python для новичков » Задача Компьютерная игра

ElmarB

Апрель 15, 2020 13:54:08

Добрый день. Помогите с заданием.
Уже всё перепробовал и передумал, никак не могу пройти тестировщика. Когда вводится 3-5 чисел то работает нормально, но как только список платформ увеличивается до 100+, то не получается высчитать количество минимальной энергии, ответ получается неверный.

Вот задача

Герою компьютерной игры нужно перебраться от одного края экрана к другому, перепрыгивая по платформам. При этом при прыжке с одной платформы на соседнюю, у героя уходит |y2-y1| единиц энергии, где y1 и y2 – высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприем, который позволяет перескочить через платформу, но на это затрачивается 3*|y3-y1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

Вам известны высоты всех платформ в порядке от левого края до правого. Необходимо найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней.

Формат входных данных
В первой строке - количество платформ (0 < n <= 30000). Далее на каждой из n строк записана высота , на которой расположена очередная платформа.

Формат выходных данных
Одно число — минимальное количество энергии, которую должен потратить герой на преодоление платформ.

Примеры
Ввод
3
1
5
10
Вывод
9

Ввод
1
1
Вывод
0

Ввод
2
20
14
Вывод
6

 # Создаем список платформ
N = int(input())
i = 0
A = []
while i<N:					
	A.append(int(input()))
	i += 1
if N>2:
	energy = [0, abs(A[1] - A[0])]+[0]*(N-2) 
	Prev = [0]*(N)
	for i in range(2,N):
		if energy[i-1] + abs(A[i] - A[i-1]) < 3*abs(A[i] - A[i-2]):
			energy[i] = (abs(A[i] - A[i-1]))
			Prev[i] = i-1
		else:
			energy[i] = (3*abs(A[i] - A[i-2]))
			Prev[i] = i-2
	
	# Идем по списпку предков и суммирум затраченную энергию
	tot_energy = 0
	k = len(A)-1
	while k > 0:
		tot_energy += energy[k]
		k = Prev[k]
	print(tot_energy)
	
elif N == 2:
	print(abs(A[1] - A[0]))
else:
	print(0)

ElmarB

Апрель 15, 2020 14:00:55

Вот скрин теста

Striver

Апрель 16, 2020 08:41:47

Как я понял по твоему коду, на каждом шаге у тебя проводится оценка, что выгоднее: прыгнуть поочерёдно 2 раза на ближайшую платформу или применить “суперприём” и перепрыгнуть через одну.
Т.е. если высоты ближайших платформ равны:

(0, 1, 2) - получаем |1-0| + |2-1| = 2 и 3*|2-0|=6, т.е. тут выгоднее прыгать по очереди
(0, 5, 1) - получаем |5-0| + |1-5| = 9 и 3*|1-0|=3, т.е. тут выгоднее перепрыгнуть через вторую платформу

Всё это кажется вполне логичным, но есть подозрение, что существуют менее очевидные случаи (они проявятся только для более длинных последовательностей платформ, чем 3), когда такого твоего алгоритма (он называется жадным) может оказаться недостаточно. Возможно, требуется пересчитать затраченную энергию для всех возможных комбинаций прыжков/суперпыжков (а таких комбинаций может оказаться мнооого), и тогда ты действительно найдёшь глобальный минимум. И, возможно, он не совпадёт с тем, что находит “жадный” алгоритм.

Koba_mk2

Июнь 6, 2020 15:43:15

Я так понимаю, вы решаете задачки Хирьянова. Перед решением этой задачи нужно было посмотреть его лекции по динамическому программированию. Попробую объяснить на рисунке и собственном коде, как она решается.
Итак, что нам нужно сделать в этой задаче? По сути, вычислить наименьшую стоимость попадания на последнюю платформу. Как это сделать? Узнать стоимость попадания на две предыдущие платформы и выбрать минимальную!
Допустим, у нас есть некоторое количество платформ, высоты которых занесены в массив P. Тогда представим, что последняя платформа у нас хранится под индексом i, а её высота равна y. На i-тую платформу мы можем попасть только с двух предыдущих платформ, т.е. с платформ i-1 и i-2. Их высоты соответственно y(i-1) и y(i-2). Стоимость перехода с одной платформы на другую мы знаем из условия задачи. Чтобы попасть на i-тую платформу с платформы i-1 нам нужно заплатить модуль разницы их высот, т.е. |y - y(i-1)|. А чтобы попасть на i-тую платформу с платформы i-2 нам нужно заплатить утроенный модуль разницы их высот, т.е. 3*|y - y(i-2)|. К данным выражениям прибавляем стоимости (пусть она будет С), которую затратили за посещение этих клеток, т.е. стоимости клетки i-1 и i-2 соответственно. Получаем следующее выражение C(i) = min(|y-y(i-1)| + C(i-1), 3*|y-y(i-2)| + C(i-2))

Ну а вот и сам код с комментариями:

 def count_min_cost(A):
	if len(A) == 1: 		# Если массив с платформами содержит всего одну платформу, то стоимость посещения последний платформы равна нулю. Прыгать никуда не надо
		return 0
	C = [0] * (len(A))		# Создаем массив со стоимостями. Его длинна будет равна длинне массива с платформами
	C[0] = 0			# В C[0] и так уже хранится "0", но для наглядности повторим: стоимость посещения самой первой платформы нулевая - прыгать никуда не надо
	C[1] = abs(A[1] - A[0])	        # Создаем стоимость посещения второй платформы
	for i in range(2, len(A)):	# Ну а после этого запускаем цикл, который расчитывает минимальную стоимость посещения каждый платформы по выведенной нами формуле =)
		C[i] = min(abs(A[i]-A[i-1]) + C[i-1], 3 * abs(A[i]-A[i-2]) + C[i-2])
	return C[-1] 			# Возвращаем последний эллемент массива, в котором хранится минимальная стоимость посещения последней платформы. Ура, мы победили! =))))) 
N = int(input()) 
P = [0] * N
for i in range(N):
	P[i] = int(input())
print(count_min_cost(P))