h1(#turnuri2). 'Turnuri2':problema/turnuri2

h1(#turnuri2). 'Turnuri2':problema/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:
 
== code(cpp) |
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.