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 (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:
 
== code(cpp) |
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.