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 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 ( int i = 1; i <= N; ++i) {
    maxi = K[i]; //maxi = coeficientul maxim pentru turnul i
    int j;
    for (j = i - 1; j > 0 && H[j] <= H[i]; j = poz[j] )
        maxi = max ( maxi, best[j] ) ;
    maxi = max ( maxi, K[j] ) ;

    best[i] = maxi ;
    poz[i] = j ;
}

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