C - VýrubČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Cestári sa rozhodli z bezpečnostných dôvodov preriediť stromoradia popri cestách. To znamená, že nechcú vyrúbať všetky stromy popri ceste, ale len niektoré. Na základe odporúčaní ochranárov je pre každú cestu stanované, aký maximálny počet stromov za sebou (susedných stromov) môže byť vyrúbaný. Zároveň kvôli estetike platí podmienka, že prvý a posledný strom pri ceste nebudú za žiadnych okolností vyrúbané. Nech je tento limit 2. Označme S ako strom a P ako vyrúbaný strom (peň stromu). Potom výrub s výsledkom SPPSSSPSSPPSPPSPPSSje prípustný, keďže prvý ani posledný strom neboli vyrúbané a súvislá podpostupnosť vyrúbaných stromov nie je nikde dlhšia ako 2. Naopak výrub SPPPSPSnie je prípustný, keďže máme úsek, kde sme vyrúbali až 3 stromy za sebou. Cestári nemajú na výrub dostatočné materiálno-technické vybavenie. Objednali si preto externú firmu, aby výrub zrealizovala. Dohoda je taká, že firma výrub zrealizuje bezplatne. Odmenou jej bude to, že drevo z vyrúbaných stromov si môže ponechať. Nie je však strom ako strom. A tak každý strom, resp. jeho drevnú hmotu, vie firma po spracovaní spenažiť za inú cenu. Firma chce samozrejme maximalizovať svoj zisk. Ktoré stromy by mala vyrúbať, aby splnila požiadavky cestárov a zároveň maximalizovala svoj zisk? ÚlohaDaný je zoznam cestných úsekov, popri ktorých treba zrealizovať výrub. Pre každý strom poznáme jeho cenu. Pre každý cestný úsek spočítajte maximálny možný zisk firmy, ak bude realizovať výrub podľa požiadaviek cestárov.VstupKaždý riadok vstupu obsahuje jednu postupnosť čísel reprezentujúcu jedno stromoradie popri cestnom úseku. Jednotlivé čísla sú oddelené medzerami. Prvé číslo v riadku N (1 ≤ N ≤ 400) určuje počet stromov v stromoradí. Druhé číslo v riadku K (0 ≤ K ≤ 20) určuje maximálny počet susedných stromov, ktoré môžu byť vyrúbané. Za ním nasleduje N čísel vyjadrujúcich ceny jednotlivých stromov, pričom každá cena stromu je nezáporné celé číslo menšie ako 5000. Vstup je ukončený riadkom, v ktorom sa nachádza číslo -1.VýstupVýstupom je v každom riadku pre zadané stromoradie vypočítaný maximálny možný zisk (súčet cien vyrúbaných stromov) firmy pri výrube stromoradia na tomto úseku podľa požiadavky cestárov.PríkladVstup:28 2 266 3343 625 2804 1879 2009 648 3816 3612 4944 4427 1096 1693 2133 4924 1010 1382 2434 593 1102 1712 2156 1324 4420 305 1966 3568 4759 31 1 4201 3148 248 4618 1003 4644 763 2090 1768 182 941 100 3978 1032 3075 4240 2638 3164 4980 4345 357 667 293 2482 1016 1222 639 2151 1370 2492 502 15 3 1232 4267 2344 2780 1851 1698 4765 3835 3143 3328 4127 3227 913 601 2117 14 0 2343 4578 3590 4323 4118 4965 4947 1548 284 3469 2476 331 119 2385 10 4 4211 2866 4180 3903 430 2305 702 2912 166 183 16 2 30 100 100 1 100 100 1 100 100 300 100 100 1 100 100 30 -1 Výstup:46826 40182 30972 0 17034 1100 |