Uite o rezolvare O(N log
2 N):
Sa notam H = |h
1-h
2| + ... + |h
n-1 - h
n| si cu SV
i = |h
i-1-h
i| - |h
i-h
i+1|.
Pentru primul si ultimul pom putem verifica liniar cu care e optim sa le inlocuim: 2 * O(N) = O(N).
Pentru un pom i, 1 < i < N, trebuie sa aflam care e cel mai bun pom j cu care putem sa il inlocuim. Calculam in O(1) valoarea inlocuirii daca j = 1 sau j = N si acum vrem sa det. 1 < j < N a. i.
H - SVi - SVj + |xj-1-xi| + |xi-xj+1| + |xi-1-xj| + |xj-xi+1| sa fie minim.
Sa consideram punctele in plan de coordonate (x
j-1, x
j) care sa aiba asociat costul x
j+1. Consideram evenimente pe axa temporala de genul:
* la momentul de timp x
j+1 adaugam punctul (x
j-1, x
j) in plan
Cand inseram punctul (x
i-2, x
i-1) de cost x
i putem afla raspunsul pe care il vrem in log
2N, tratand niste cazuri. Putem presupune de ex. ca x
i apartine intervalului [x
j-1, x
j+1] si ca x
i-1 < x
j. Asta determina un dreptunghi in plan si o expresie fixa in functie de j care trebuie minimizata => arbore de intervale 2D cu memorie O(N log N). Mai clar probl se rezuma la:
Ai n puncte in plan si operatii de forma: "pune un punct in plan de cost dat" si "afla intr-un dreptunghi care e costul minim". Poti folosi ideea de la arborele 2D de
aici, numai ca tu trebuie sa tii pe fiecare nivel (logN nivele in total) cate un alt arbore de intervale, nu un simplu vector, ca sa poti face si query si update
.
E cam jegos de implementat si e destul de incalcita solutia, mai ales ca ai vreo 6 cazuri
. S-ar putea sa existe si o solutie mai buna, asta a fost insa prima idee care mi-a venit
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena