コスト付き階段
あなたは現在、
n 段ある階段を上っています。各ステップで、2 段進むか 1 段進むかを選ぶことができます。階段の各段に足を踏み入れるたびに、その段に対応するコストを支払わなければなりません。あなたの目標は、合計の支払いコストをできる限り抑えながら、最上段までたどり着くことです。入力
最初の行には、整数
n (1 ≤ n ≤ 1000) が 1 つ与えられます。次の行には、それぞれの段に対応するコスト (0 ≤ ≤ 1000) が与えられます。
出力
階段の最上段に到達するために支払う最小のコストを出力してください。
例
入力 | 出力 |
3
10 12 25 | 12 |
10
1 20 1 1 1 20 1 2 20 1 | 7 |
解説
- 階段の手前にいる時点ではコストは 0。2 段目に上がるとコストが 12 になる。その後、2 段進むステップで階段から抜け出せば、コストは 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