Płot - zadanie z XII OIG

Question

Cześć,

niedawno natknąłem się na zadanie z XII Olimpiady Informatycznej Gimnazjalistów o nazwie "płot". Chodzi w nim o to, że na wejściu podaną mamy liczbę n (1 <= n <= 200 000), a następnie n liczb, z których każda jest nie mniejsza od 1 i nie większa od 10^6. Trzeba usunąć niektóre liczby, tak aby suma pozostałych była jak największa i aby wartości pozostawionych liczb na zmianę rosły i malały.

Np. dla danych wejściowych:

6

7 5 4 6 6 5

rozwiązaniem jest 23, gdyż wystarczy usunąć 4 i jedno 6.

Myślałem nad tym zadaniem godzinę i nie mam żadnego pomysłu. Patrząc na zakres wartości n, wydaję mi się, że rozwiązanie może mieć złożoność około O(n log n), ale nie jestem pewien. Bardzo prosiłbym o nakierowanie na poprawne rozwiązanie.

Comments

A myślałeś nad brutem? Często wzorcówki to optymalizacje brutów.

Co to znaczy na zmianę rosły i malały? W sensie jest ciąg od początku do k który rośnie i od k do końca który maleje tak?

Answer 1

Nie do końca rozumiem treści ale mogę dać podpowiedź, która się pewnie przyda.

Za pomocą kolejki monotoniczności możesz wyznaczyć w czasie liniowym pierwszy indeks na prawo elementu który jest większy od i-tego oraz tak samo z mniejszym.

Comments

Dzięki za odpowiedź. Jeżeli chodzi o treść zadania to wraz z otoczką fabularną brzmi ono tak: 

Pan Paweł jest rolnikiem i zbudował ogrodzenie swojego gospodarstwa. Składa sie ono z n sztachet, których wysokości opisuje ciąg an. Rolnik postanowił jednak zmienic wyglad swojego płotu tak, aby wysokości kolejnych sztachet w jego płocie na zmiane rosły i malały. Dodatkowo, Pan Paweł ceni sobie prywatnosc i dazy do tego, aby suma długosci pozostałych w płocie sztachet była jak największa. W tym celu mężczyzna musi usunąc z ogrodzenia niektóre sztachety. Napisz program, który obliczy maksymalną sume długosci sztachet pozostałych w płocie.

Więc te sztachety mają być według schematu: większa, mniejsza, większa, mniejsza, większa, mniejsza itd.

---

No to pierwsze przechodzisz po tablicy i kolejką monotoniczności wyznaczasz dla każdego elementu pozycję mniejszego na lewo i większego na lewo.

A następnie puszczasz dynamika, coś w tym rodzaju:

dp[i] = max(dp[i-1],

max( dp[posmniejszego[i]]+val[i], dp[poswiekszego[i]]+val[i]) );

ale trzeba jeszcze jakoś pamiętać żeby nie wzięło 2 razy większego pod rząd, może dołożyć jeszcze jeden wymiar i pod 0 trzymać najlepszy wynik gdzie kolejny musi być większy, a pod 1 gdzie kolejny musi być mniejszy.

 zadanie wydaje mi się nie takie proste jak na oig

---

Dzięki za odpowiedź. Rzeczywiście twoje rozwiązanie będzie działać. W międzyczasie natomiast wpadłem na inny pomysł, choć bardzo podobny.

Tablica arr zawiera wszystkie wysokości sztachet z wejścia.

Dla każdej i-tej liczby od 0 do n-1 będę rozważał dwa przypadki, gdy jest większa od pewnej poprzedniej wartości i gdy jest mniejsza. Powiedzmy, że w tablicy dp_wieksza[i], wyznaczę maksymalną sumą pewnych wybranych wartości od 0 do i włącznie, a i musi być większe od poprzedniej wybranej wartości. Tak samo w dp_mniejsza[i], tylko i musi być mniejsze od poprzednio wybranej wartości. Teraz aby wyznaczyć dp_wieksza[i] liczę sumę z arr[i] i maksymalnej wartości z tablicy dp_mniejsza (dla tablicy dp_mniejsza rozważam wszystkie indeksy j , z czego 0<= j < i) i trzbeba pamiętać, aby wybrana wartość arr[j] była mniejsza od arr[i]. Podobnie robie dla dp_mniejsza tylko szukam maksa z dp_wieksza i wartość arr[j] ma być większa od arr[i].

Żeby szybko wyznaczać maksymalne wartości utworzę dwie dodatkowe tablice (o nazwach mniejsza i większa) o rozmiarach 10^6, początkowo wypełnione samymi zerami. Gdy oblicze jakieś dp_wieksza[i] lub dp_mniejsza[i] do tablicy wieksza[arr[i]-1] wstawiam dp_wieksza[i] i tak samo dla dp_mnijesza. Teraz na tablicach wieksza i mniejsza buduje drzewo przedziałowe, co pozwala mi szybko znajdować maksymalne wartości. Czyli gdy licze dp_wieksza[i] to szukam maksa w tablicy mniejsza na przedziale od 0 do arr[i]-2, a gdy liczę dp_mniejsza[i] to szukam maksa w tablicy wieksza na przedziale od arr[i] do 10^6.

Rozwiązanie troszkę skomplikowane i rzeczywiście zgadzam się z tobą, że to zadanie było dość trudne jak na OIG.

---

a wkleiłbyś kod twojego rozwiązania(o ile je jeszcze masz), napiszę sobie sprawdzarkę i sprawdzę, czy mój kod jest dobry.

---

Niestety nie mam kodu. Pewnie go nie napisałem bo i tak nie byłoby gdzie go wysłać

Answer 2

Gdzie znalazłeś to zadanie?

Ja nie mogłem znalezc zadań z późniejszych edycji OIG niz 6.

Comments

startowałem w tej edycji OIG, więc miałem akurat ich treści. To było jedno z zadań których nie umiałem rozwiązać podczas I etapu