Escada com custo
Estamos a subir uma escada com
n degraus. A cada passo, podes subir 2 degraus ou apenas 1. Ao pisares cada degrau, pagas um custo associado a esse degrau. O teu objetivo é chegar ao topo da escada pagando o menor valor possível.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 1000).A linha seguinte contém os custos associados a cada degrau (0 ≤ ≤ 1000).
Saída
O programa deve imprimir o custo mínimo para chegar ao topo da escada.
Exemplos
Entrada | Saída |
3
10 12 25 | 12 |
10
1 20 1 1 1 20 1 2 20 1 | 7 |
Explicação
- Estamos em frente à escada ⇒ o custo atual é 0. Subimos para o segundo degrau ⇒ o custo passa a ser 12. Em seguida, deixamos a escada com um passo de 2 degraus ⇒ o custo mantém-se 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