Escalera con costo
Estás subiendo una escalera con
n escalones. En cada movimiento, puedes subir 2 escalones o solo 1. Cada vez que te paras en un escalón, pagas un costo asociado a ese escalón. Tu objetivo es llegar hasta la parte superior de la escalera pagando la menor cantidad posible.Entrada
La primera línea de la entrada contiene un solo número entero
n (1 ≤ n ≤ 1000).La siguiente línea contiene los costos asociados a cada escalón (0 ≤ ≤ 1000).
Salida
El programa debe imprimir el costo mínimo para llegar a lo más alto de la escalera.
Ejemplos
Entrada | Salida |
3
10 12 25 | 12 |
10
1 20 1 1 1 20 1 2 20 1 | 7 |
Explicación
- Estamos frente a la escalera ⇒ el costo actual es 0. Subimos directamente al segundo escalón ⇒ el costo es 12. Luego dejamos la escalera con un paso de longitud 2 ⇒ el costo se mantiene en 12.
- 1 20 1 1 1 20 1 2 20 1 ⇒
120 1 1 1 20 1 2 20 1 ⇒ 1 2011 1 20 1 2 20 1 ⇒ 1 20 1 1120 1 2 20 1 ⇒ 1 20 1 1 1 2012 20 1 ⇒ 1 20 1 1 1 20 1220 1 ⇒ 1 20 1 1 1 20 1 2 201⇒ 7
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB