h3. (problema usoara, clasa a 9-a)

La primul pas se vor sorta orasele crescator dupa $D{~i~}$. Renumerotand orasele in ordinea sortarii, putem calcula distanta care trebuie parcursa intre doua orase $j < i$: $L{~i~}+D{~i~}+L{~j~}-D{~j~}$. Pentru fiecare $i$ vrem sa determinam un oras $j < i$ astfel incat sa se maximizeze aceasta distanta. Alegerea optima va fi un oras $j$ cu valoarea $L{~j~}-D{~j~}$ maxima; astfel, pe masura ce se avanseaza cu indicele $i$ se pastreaza si un indice $j$ maxim pana in prezent. Complexitatea rezolvarii este $O(N*lg N)$ datorita sortarii.

La primul pas se vor sorta orasele crescator dupa $D{~i~}$. Renumerotand orasele in ordinea sortarii, putem calcula distanta care trebuie parcursa intre doua orase $i < j$: $L{~i~}+D{~i~}+L{~j~}-D{~j~}$. Pentru fiecare $i$ vrem sa determinam un oras $j < i$ astfel incat sa se maximizeze aceasta distanta. Alegerea optima va fi un oras $j$ cu valoarea $L{~j~}-D{~j~}$ maxima; astfel, pe masura ce se avanseaza cu indicele $i$ se pastreaza si un indice $j$ maxim pana in prezent. Complexitatea rezolvarii este $O(N*lg N)$ datorita sortarii.

h2. 'Sarpe':problema/sarpe