Zadanie

KSPáci boli na chate a keďže málo z nich má plne vyvinutú jemnú motoriku, tak sa im na schodoch vždy podarí niečo vyliať. Na polke schodu je lekvár, na druhej zas Kofola™. Na ďalšom zas Nutella™ a kečup…

Filipkovi síce nepadajú veci z rúk ale za to si na chatu zvládol zobrať len jeden pár ponožiek. Chcel by sa teda večer dostať do izby, s čo najmenej zašpinenými ponožkami. Viete mu s tým pomôcť?

Úloha

Chata má n schodov. Každý schod má dve polovice. Na každej polovici je rozliate niečo, čo Filipkovi zašpiní ponožky. Pre každý schod teda poznáme dve čísla:

  • ľavá strana: koľko špiny spôsobí, keď na ňu stúpi
  • pravá strana: to isté, ale pre pravú polovicu

Filipko môže na začiatku začať buď na prvom alebo druhom schode, a ľubovoľnou nohou (ľavou alebo pravou). Potom ide hore po schodoch, pričom sa môže pohnúť buď o jeden schod (napr. zo schodu 2 na 3) alebo dva schody (napr. z 2 na 4). Musí striedať nohy – ak posledný krok spravil ľavou, ďalší musí pravou, a naopak. Musí skončiť presne na poslednom schode (čiže sa nesmie zastaviť skôr ani ho preskočiť).

Vašou úlohou je zistiť, aké najmenšie množstvo zašpinenia ponožiek môže Filipko utrpieť, ak sa chce po zafŕkaných schodoch dostať z dolného poschodia na posledný schod, teda najmenší možný súčet zašpinení na polovicach schodov, na ktoré stúpi.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(2 \leq n \leq 5 \cdot 10^5\)) udávajúce počet schodov na chate.

Potom budú nasledovať dva riadky s \(n\) číslami oddelenými medzerou. Prvý pre ľavú stranu a druhý pre pravú. \(i\)-te číslo v riadku prezenovať zašpinenie \(i\)-teho schodu na danej strane. Pre každé číslo zašpinenia platí: \(0 < l_i, p_i \leq 1000\).

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
\(1 \leq N \leq\) \(15\) \(100\) \(5\,000\) \(500\,000\)

Formát výstupu

Vypíšte jedno číslo - najnišie možné zašpinenie ponožiek.

Príklady

Input:

4
1 2 2 1
2 1 3 2

Output:

2

Filipko preskočil prvý schod a skočil pravou nohou rovno na druhý s hodnotou 1. Odtiať už dočiahol skočiť na posledný schod ľavou nohou s hodnotou 1, teda dokopy 2.

Input:

5
1 4 5 1 5
1 7 2 2 3

Output:

7

1. schod ľavá noha(1), 3. schod pravá noha(2), 4. schod ľavá noha(1), 5. schod pravá noha(3): 1 + 2 + 1 + 3 = 7.

Pozorvanie

Zadanie hovorí dve zaujímavé veci:

  • Filipko môže začať na ľubovoľnom z prvých dvoch schodov.
  • Môže vykročiť ľubovoľnou nohou, ale od toho momentu musí striedať nohy pri každom kroku.

To znamená, že na každom schode nás zaujímajú dve hodnoty: aké je minimálne zašpinenie, ak naň Filipko stúpi ľavou nohou, a to isté pre pravú nohu.

Naivné riešnie

Najpriamočiarejšie riešenie je prejsť všetky možné cesty, ktorými sa vieme dostať na posledný schod. Začneme na jednom z prvých dvoch schodov a ľubovoľnou nohou. V každom kroku máme na výber ísť o jeden alebo o dva schody vyššie; tým sa automaticky určí, ktorou nohou stúpime na nový schod a akú hodnotu zašpinenia k výsledku pripočítame. Takto rekurzívne preskúmame všetky kombinácie krokov, na konci si vyberieme najmenší nájdený súčet. Tento postup síce vždy nájde správnu odpoveď, ale má exponenciálnu časovú zložitosť \(O(2^n)\).

Vzorové riešenie

Túto úlohu budeme riešiť dynamickým programovaním.

Pre každú nohu si budeme postupne dorátavať optimálne hodnoty. A to tak, že postupne budeme dorávať hodnotu na aktuálnom schode pomocou hodnoty na predchádzajúcich schodoch.

Definujeme si dve polia:

  • dl[i] — najmenšie zašpinenie, ak Filipko skončí na i-tom schode a stúpi naň ľavou nohou
  • dp[i] — to isté, ale pre pravú nohu

Aby sme mohli vypočítať dl[i], musíme sa sem nejako dostať. Keďže striedame nohy, vieme sem prísť len s pravou nohou, a to:

  • buď zo schodu i-1, teda dp[i-1] + l[i]
  • alebo zo schodu i-2, teda dp[i-2] + l[i]

Analogicky pre pravú stranu schodov.

Ešte potrebujeme vyriešiť začiatočné prípady pre prvé dva schody na oboch stranách. O tých vieme rovno povedať, že to budú určite hodnoty len daných schodov, keďže sa na ne dokážeme dostať jedným krokom – teda priamo na ne. Teda dp[0] = p[0]; dp[1] = p[1] a podobne pre ľavú nohu.

Potom dynamicky zostavujeme riešenie od najnižšieho schodu k najvyššiemu. Na posledný schod n-1 musíme došliapnuť, ale môžeme naň stúpiť ľavou alebo pravou nohou — vyberieme teda minimum: \(min(d_l[-1], d_p[-1])\).

Prečo to funguje ?

Správnosť riešenia vyplýva z toho, že dl[i] a dp[i] vždy uchovávajú minimálne možné zašpinenie pri skončení na \(i\)-tom schode ľavou, resp. pravou nohou. Pre prvé dva schody vieme tieto hodnoty určiť priamo, keďže na ne môžeme vstúpiť jediným krokom. Pre každý ďalší schod sa môžeme naň ľavou nohou dostať len z pravou nohou na \(i-1\) alebo \(i-2\) (aby sme dodržali striedanie nôh a povolené kroky), takže optimálna hodnota dl[i] je \(min(dp[i−1],dp [i−2])+l[i]\) , a analogicky pre dp[i]. Keďže rekurencia zohľadňuje všetky možné prípady a vždy berie minimum, výsledok \(min(dl[n−1],dp[n−1])\) je skutočne globálne najmenšie možné zašpinenie.

Zložitosť

Časová zložitosť: \(O(n)\) — pre každý schod spravíme konštantný počet operácií.

Pamäťová zložitosť: \(O(n)\) — ukladáme si dve hodnoty pre každý schod.

Optimalizácia: Ak potrebujeme ešte menej pamäte, môžeme si namiesto celých polí dl a dp pamätať len posledné dve hodnoty. Keďže na výpočet dl[i] a dp[i] používame iba hodnoty z \(i-1\) a \(i-2\), staršie nepotrebujeme. Preto si stačí pamätať len tieto dve posledné hodnoty pre každú nohu a zvyšok môžeme zahodiť.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.