Ալգորիթմներ և Տվյալների Կառուցվածքներ

Աստիճաններ ծախսով

Դուք բարձրանում եք n աստիճաններով: Յուրաքանչյուր քայլն կարող եք բարձրանալ կա՛մ 2 աստիճան, կա՛մ՝ 1: Ամեն անգամ, երբ ոտք եք դնում աստիճանի վրա, վճարում եք տվյալ աստիճանի համար սահմանված գումարը: Ձեր խնդիրն է հասնել ամենավերև՝ ծախսելով հնարավորինս քիչ գումար:

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 1000):
Հաջորդ տողում տրված են աստիճանների ծախսերը (0 ≤ ≤ 1000):

Ելք

Ծրագիրը պետք է տպի ամենավերև հասնելու նվազագույն հնարավոր ծախսը:

Օրինակներ

Մուտք
Ելք
3 10 12 25
12
10 1 20 1 1 1 20 1 2 20 1
7

Բացատրություն

  1. Սկզբնական պահին կանգնած ենք աստիճանների դիմաց, ուստի ծախսը 0 է: Այնուհետև բարձրանում ենք երկրորդ աստիճան (ծախսը դառնում է 12), իսկ հաջորդ քայլով (2 աստիճան) դուրս ենք գալիս աստիճանահարթակից, և ծախսը մնում է 12:
  1. 1 20 1 1 1 20 1 2 20 1 ⇒ 1 20 1 1 1 20 1 2 20 1 ⇒ 1 20 1 1 1 20 1 2 20 1 ⇒ 1 20 1 1 1 20 1 2 20 1 ⇒ 1 20 1 1 1 20 1 2 20 1 ⇒ 1 20 1 1 1 20 1 2 20 1 ⇒ 1 20 1 1 1 20 1 2 20 1 ⇒ 7։
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue