Užsispyrusi varlytė
시간 제한1초메모리 제한1024 MB
수련잎 0에서 출발해 한 번에 최대 L칸까지 뛰어 물가에 도착할 때, 각 수련잎 i에 내려앉는 데 드는 l_i분의 합을 최소로 만드는 경로를 찾는다.
문제
Po šaltos žiemos, ištirpus ledui, varlių šeimynėlė išsirengė prie kūdros. Kūdra neteko nusivilti – vanduo nešaltas ir virš kūdros dūzgia daugybė musių. Tad visos mažos varlytės buvo laimingos galėdamos visą dieną taškytis vandenyje.
Atėjus vakarui, varlyčių Mamai teko sunkus darbas – sukviesti visas varlytes į krantą. Jos kvietimui pakluso visos varliukės, išskyrus mažiausiąją.
Lelijų lapai auga tiesia linija ir yra sunumeruoti nuo 0 nuo kūdros link kranto. Mažiausioji varlytė tupi ant lapo, kurio numeris 0. Jos maksimalus šuolio ilgis yra L, t. y. tupėdama ant lapo, kurio numeris yra k, varlytė gali nušokti ant lapų, kurių numeriai yra k + 1, k + 2, . . . , k + L.
Virš kiekvieno lelijos lapo zvimbia tam tikras musyčių skaičius. Užsispyrusi varlytė sutinka judėti link kranto tik jei galės sugauti visas musytes, zvimbiančias aplink kiekvieną lapą, ant kurio ji užšoks pakeliui į krantą.
Varlytė šokinėja labai greitai, todėl šokinėjimui sugaišto laiko neskaičiuokime. Tačiau sugauti ir praryti vieną musytę užtrunka vieną minutę.
1 pav. Keli galimi varlytės šokinėjimo scenarijai
Panagrinėkime pavyzdį, kai kūdroje yra 5 lelijos (N = 5).
Mūsų užsispyrėlė tupi ant lelijos, kurios numeris yra 0, ir gali nušokti iki 2 lelijų tolyn (L = 2). Virš pirmosios lelijos skraido 1 musė, virš antrosios – 3, virš trečiosios – 3, o virš ketvirtosios – 2 musės (žr. pav. 1).
Paveikslėlyje pavaizduoti du būdai, kaip varlytė gali pasiekti krantą.
Vienu atveju varlytė šoka ant lelijos, kurios numeris 2, ir randa 3 musytes. Joms pagauti sugaiš 3 minutes. Tuomet ji šoka ant lelijos, kurios numeris 4, ten randa dvi musytes, o tuomet trečiu šuoliu pasiekia krantą. Taigi, ji krantą pasiekia per 5 minutes.
Kitu atveju varlytė šoka ant pirmos lelijos, randa 1 musytę, tuomet šoka ant trečios lelijos ir sugauna 3 musytes, ir paskutiniu šuoliu pasiekia krantą. Šiuo atveju ji krantą pasiekia per 4 minutes.
Raskite šokinėjimo kelią, kuris leistų užsispyrėlei atsirasti ant kranto per trumpiausią įmanomą laiką.
입력
Pirmoje eilutėje pateikiami du skaičiai: lelijų skaičius N ir maksimalus šuolio ilgis L.
Antroje eilutėje pateikiama N − 1 sveikųjų skaičių: l1, l2, l3, . . . , lN−1, kur li nurodo, kiek musių skraido virš lelijos, kurios numeris yra i (1 ≤ i ≤ N − 1).
Užsispyrusi varlytė pradžioje tupi ant lelijos, kurios numeris yra 0. Virš šios lelijos musių nėra.
출력
Išveskite vieną skaičių – per kiek mažiausiai minučių varlytė gali pasiekti krantą.