h1(#panza). 'Solutia problemei Panza':problema/panza

Solutia pleaca de la construirea unui tablou bidimensional $d$, in care $d[i][j]$ are semnificatia urmatoare: lungimea minima a unui drum care pleaca din punctul $S$ de pe primul segment, ajunge pe segmentul $i$ in punctul $j$ si trece prin fiecare interval cu vitamine pentru toate segmentele de la $1$ la $i$. Astfel putem simula constructia unui drum de lungime cat mai mica. Pentru initializare, $d[ 1 ][i] = |i - S|$, pentru calcul efectiv, vom folosi recurenta ce urmeaza sa fie descrisa, iar pentru raspunsul final vom fi interesati in valoarea minima ce poate fi obtinuta alegand convenabil o valoare $pos$ si gasind solutia $d[N][pos] + |pos - F|$.

Solutia pleaca de la construirea unui tablou bidimensional $d$, in care $d[i][j]$ are semnificatia urmatoare: lungimea minima a unui drum care pleaca din punctul $S$ de pe primul segment, ajunge pe segmentul $i$ in punctul $j$ si trece prin fiecare interval cu vitamine pentru toate segmentele de la $1$ la $i$. Astfel putem simula constructia unui drum de lungime cat mai mica. Pentru initializare, $d[1][i] = |i - S|$, pentru calcul efectiv, vom folosi recurenta ce urmeaza sa fie descrisa, iar pentru raspunsul final vom fi interesati in valoarea minima ce poate fi obtinuta alegand convenabil o valoare $pos$ si gasind solutia $d[N][pos] + |pos - F|$.

Pentru recurenta, presupunand ca am calculat $d[i - 1][p]$, pentru oricare $p$ intre $X[i - 1]$ si $Y[i - 1]$, vom dori sa calculam $d[i][j]$, pentru oricare $j$ intre $X[i] si Y[i]$. Trebuie sa fim atenti, deci, sa nu consideram drumuri care nu iau vitamina $i$ sau $i - 1$.