B3 - Branje
Vremensko ograničenje | Memorijsko ograničenje |
---|---|
1500ms | 64MB |
Stiglo je proleće, visibabe su uveliko počele da rastu, a gazda Srba želi da to iskoristi i da profitira prodavajući visibabe ljudima u gradu koji nemaju dvorište, a žele da se raduju ovom prvom prolećnom cveću.
U svom dvorištu Srba ima \(N\) visibaba poređanih u red, i za svaku je odredio, gledajući njenu lepotu, koliko dinara može da zaradi ako je proda.
Pošto ima mnogo visibaba, a Srba je malo lenj, on je kupio dve mašine (visibaboberače) koje će ih brati umesto njega. Ipak, mašine zahtevaju struju, i što je veća visibaba mašina zahteva više potrošnje. Srba je za svaku visibabu izračunao koliko će u dinarima platiti struju ako bi je mašina obrala. Da bi dodatno uštedeo, Srba neće da stalno gasi i pali mašine, već će ih samo jednom upaliti, pustiti svaku od njih da obere neki broj uzastopnih visibaba, i zatim ugasiti. Pri tome, obe mašine moraju da budu uključene za neku uzastopnu grupu visibaba (za barem jednu visibabu), a te grupe ne smeju da sadrže nijednu istu visibabu.
Pomozite Srbi da ostvari najveći profit, računajući dobit od prodavanja visibaba i trošak na struju za branje.
Ulaz
U prvom redu standardnog ulaza se nalazi broj \(N\) koji predstavlja broj visibaba u Srbinom dvorištu. U drugom redu se nalazi niz od \(N\) brojeva \(Z_i\) gde \(i\)-ti broj predstavlja koliko će Srba zaraditi ako proda \(i\)-tu visibabu. U trećem redu se nalazi niz od \(N\) brojeva \(S_i\) u kome \(i\)-ti broj označava koliko će dinara potrošiti na struju ukoliko bere \(i\)-tu visibabu.
Izlaz
U prvi i jedini red standardnog izlaza ispisati jedan broj – koliko Srba najviše može da zaradi. Obratite pažnju da ovo može biti i negativan broj, ukoliko će Srba u svakom slučaju više izgubiti na struju nego na prodaju.
Primer 1
Ulaz
Izlaz
Primer 2
Ulaz
Izlaz
Objašnjenje primera
U prvom primeru, jedno od rešenja gde dobijamo najveći profit je ako prvu mašinu pustimo da obere samo \(4\). visibabu (profit je \(10 = 14 – 4\)), a drugu mašinu pustimo da obere od sedme do devete visibabe (profit je \(9 = (11 + 3 + 8) – (4 + 5 + 4))\), pa je ukupan profit \(9 + 10 = 19\).
U drugom primeru nemamo izbora osim da prvu mašinu pustimo da obere prvu visibabu, a drugu mašinu da obere drugu, gde ćemo kod prve visibabe izgubiti \(2\) dinara, a kod druge zaraditi \(1\) dinar, pa je ukupna zarada \(-1\).
Ograničenja
- \(2\leq N\leq 10^6\).
- \(0\leq Z_i\leq 10^9\).
- \(0\leq S_i\leq 10^9\).
Test primeri su podeljeni u četiri disjunktne grupe:
- U test primerima vrednim \(20\) poena važi \(N\leq 50\).
- U test primerima vrednim \(20\) poena važi \(N\leq 500\).
- U test primerima vrednim \(20\) poena važi \(N\leq 5000\).
- U test primerima vrednim \(40\) poena nema dodatnih ograničenja.
Autor | Tekst i test primeri | Analiza rеšenja | Testiranje |
---|---|---|---|
Dušan Zdravković | Dušan Zdravković | Nemanja Majski | Boris Grubić |
Uprošćavanje problema
Recimo da smo sekli neku visibabu \(i\). Primetimo da profit od njenog sečenja ne zavisi od toga koje visibabe sem nje smo odsekli, nego je uvek \(Z_i-S_i\). Taj profit ćemo pamtiti u novom nizu \(P_i=Z_i-S_i\).
Sada je naš zadatak da podelimo niz \(P\) u \(K=2\) disjunktna uzastopna podniza tako da je zbir elemenata u njima maksimalan.
Rešenje za \(N \le 50\)
U ovom podzadatku je dovoljno ručno proveriti sve moguće podele niza na podnize. Vremenska složenost je \(O(N^4)\).
Rešenje za \(N \le 500\)
U ovom podzadatku ćemo ići po desnoj granici levog podniza. Sada treba shvatiti da će leva granica levog podniza biti takva da je zbir brojeva u levom podnizu maksimalan. Nju možemo naći preko jedne petlje. Nakon toga radimo dvostruku petlju po svim mogućim desnim podnizovima. Vremenska složenost je \(O(N^3)\).
Rešenje za \(N \le 5000\)
Za svaku poziciju u nizu ćemo prekalkulisati najveći mogući zbir podniza koji počinje \(R_i\) i najveći mogući zbir podniza koji završava u toj poziciji \(L_i\). To možemo da uradimo preko dvostruke petlje.
Sada radimo dvostruku petlju po desnoj granici levog podniza i levoj granici desnog podniza. Ako smo izabrali granice \(i\) i \(j\) \((i <j)\), onda je najbolja moguća vrednost takvog izbora \(L_i + R_j\).
Vremenska složenost je \(O(N^2)\).
Rešenje za \(K=1\)
Ovo nije podzadatak u originalom zadatku, ali je važno da ga razumemo kako bismo razumeli glavno rešenje. U ovom podzadatku nam je dat niz i treba da nađemo najveći mogući zbir nekog podniza.
Možemo da održavamo \(dp[i]\) niz, gde je \(dp[i]\) najveća vrednost podniza koji se završava na \(i\). Osnovni slučaj je \(dp[0]=0\). Ako smo izračunali \(dp[k-1]\), onda je \(dp[k]=max(dp[k-1],0)+p[k]\), zato što možemo ili da nastavimo prethodni podniz, ili da započnemo novi.
Rešenje zadatka je najveća vrednost nekog elementa u \(dp\) nizu. Vremenska složenost je \(O(N)\).
Glavno rešenje
Korišćenjem rešenja za \(K=1\) možemo da kreiramo \(dp\) niz. Sada ćemo da imamo niz \(L_i\) takav da je \(L_i=max(dp_1, dp_2, dp_3, ... ,dp_{i-1}, dp_i)\). To znači da ako se desni kraj levog podniza nalazi negde pre ili na poziciji \(i\), maksimalan zbir levog podniza je \(L_i\).
Slično možemo da odredimo \(R_i\) za desni podniz. I sada samo treba da prođemo kroz svako \(1\le i <N\) i nađemo najveće \(L_i + R_{i+1}\). Vremenska složenost je \(O(N)\).
Bonus: Rešite ovaj zadatak kada je \(K \le N\). Takav zadatak nije po programu državnog takmičenja, ali može da se pojavi na SIO.
03_branje.cpp | |
---|---|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
|