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.

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.

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:

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;

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.