infoarena informatica de performanta

Stalpi

Vom sorta stalpii dupa coordonata X si vom calcula best[n] = costul minim pentru a acoperi primii n stalpi (dupa sortare). De asemenea vom sorta stalpii dupa valoarea X+D si aceasta va fi ordinea in care ii vom procesa. Cand procesam stalpul i (din ordinea sortata dupa X+D) vom afla R, cel mai din dreapta stalp pentru care X_R ≤ X_i+D_i si L, cel mai din dreapta stalp pentru care X_L < X_i-S_i. Atunci o valoare posibila pentru best[ R ] ar fi min(best[L], best[L+1]...best[N])+cost[i]. Daca best[ R ] si-a imbunatatit vechea valoare (initial vectorul best va fi initializat cu infinit) atunci pentru 1≤j≤R best[j]=min(best[j],best[ R ]). Pentru a implementa eficient operatiile descrise se poate folosi un arbore de intervale, sau mai simpu de implementat, un arbore indexat binar.