Attachment 'stairs.py'

Download

   1 #!/usr/bin/env python
   2 # coding: utf
   3 '''
   4 «Платная лестница» (MCCME) Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
   5 '''
   6 
   7 # Пусть f - функция динамического программирования. На i-ю ступеньку мальчик мог попасть только с (i-1)-й или с (i-2)-й ступенек. Значит f[i] = min(f[i-1], f[i-2]) + стоимость i-й ступеньки.
   8 
   9 # Обратите внимание на то, что по условию задачи 
  10 # на последнюю ступеньку наступать обязательно
  11 
  12 Stairs=[int(n) for n in raw_input().split()]
  13 N=len(Stairs)
  14 
  15 Price=[Stairs[0],Stairs[1]]+[-1]*(N-2)
  16 for i in xrange(2,N):
  17     Price[i]=Stairs[i]+min(Stairs[i-1],Stairs[i-2])
  18 print Stairs[-1]

Attached Files

To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.

You are not allowed to attach a file to this page.