Наступить на k-ю ступень лестницы A стоит Ak монет. Ввести через запятую «цены» ступеней A, и на следующей строке — ширину шага S (все числа натуральные) и вывести минимальную стоимость пути с земли до последней ступени (на которую наступать обязательно), при условии, что идти можно только вверх и перешагивать можно не более, чем через S-1 ступень.

Спойлер. На k-ю ступень можно добраться только с предыдущих S ступеней. Значит, минимальная стоимость пути Amink = Ak + min(Amink-1, Amink-2, … , Amink-S). Заполняем Amin в цикле, выводим последний элемент.

5, 3, 6, 1, 1, 2, 3, 4, 7, 5, 5, 7, 1, 1, 4, 6, 3, 4, 7, 4, 2
4

14


CategoryHomework

Lectures/PythonIntro/Homework_PaidStairs (last edited 2015-03-03 22:59:47 by localhost)