Turnuri2

O solutie brute-force ar fi: pentru o cladire i, 1<=i<=N verificam in stanga si respectiv dreapta coeficientul de frumusete maxim, cat timp avem cladiri de inaltimi mai mici.

Solutia optima pleaca de la soutia brute-force, cu o optimizare. Pentru o pozitie i, retinem pozitia j, cu semnificatia ca j este cel mai din stanga (drepata) turn pe care il vad de pe turnul i. Daca am calculat pentru o cladire j coeficientul de frumusete maxim pe care il are, atunci pentru pasul curent, i, mergem inapoi pe aceste pozitii, atata timp cat inaltimea acestor turnuri nu o depaseste pe cea curenta si luam maximul dintre acele coeficiente maxime.

Algoritmul in C++ pentru partea din stanga arata in felul urmator:

for (i=1; i<=n; ++i)
    k_max=K[i]; //max = coeficientul maxim pentru turnul i
    for (j=i-1; j>=1 && H[i]>=H[h]; j=poz[j])
        k_max=maxim (k_max,best[j]);
    k_max=maxim (k_max,K[j]);

    best[i]=k_max;
    poz[i]=j;

Se executa algoritmul si pentru partea din dreapta, si se obtine solutia.