- Language:
- Time limit: 1.00 s
- Memory limit: 512 MB
Lumimyrsky on iskenyt laskettelukeskukseen ja rinteet kaipaavat pikaista aurausta.
Laskettelukeskus koostuu rinteestä. Rinteet on yhdistetty toisiinsa yhteensä polulla siten, että rinne on huipulla ja sieltä on alaspäin kulkeva reitti kaikille muille rinteille.
Lumiauralla voi kulkea rinteitä ja polkuja ainoastaan alaspäin ja aurata matkalle sattuvat rinteet. Jokaisesta rinteestä on tiedossa tarvittavien aurauskertojen määrä.
Lennätät helikopterilla lumiauroja vuoren huipulle. Mikä on pienin määrä lumiauroja, jolla kaikki rinteet saadaan aurattua?
Syöte
Ensimmäisellä rivillä on kokonaisluku : rinteiden määrä.
Seuraa riviä lukuja ja : rinteeltä on polku rinteelle . Rinteet on numeroitu .
Viimeisellä rivillä on lukua : tarvittavien aurauskertojen määrä rinteille .
Tuloste
Tulosta yksi kokonaisluku: pienin tarvittava määrä lumiauroja.
Esimerkki
Syöte:
5 1 2 1 3 3 4 3 5 0 2 4 3 1
Tuloste:
6
Selitys: Laskettelukeskus on havainnollistettu kuvassa.
lumiauraa kulkee reitin , lumiauraa reitin ja 1 lumiaura reitin .