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$.

h2. <tex> O(N * M) </tex> - $100$ de puncte

Ne bazam pe faptul ca $A{~i-1~} &le; A{~i~}$, pentru orice {~i~}. De asemenea, vom face cateva calcule intermediare de complexitate <tex> O(M) </tex> pentru fiecare segment, astfel:

Vom face cateva calcule intermediare de complexitate <tex> O(M) </tex> pentru fiecare segment, astfel:

Mai intai calculam $x[j]$ care e costul minim sa ajung in punctul $j$ pe segmentul $i - 1$, stiind ca prin punctul $j$ trec, pe punctea de lungime $A[j]$, pe segmentul $i$. Pentru inceput, $x[j] = d[i - 1][j]$, daca $X[i - 1] ≤ j ≤ Y[i - 1]$, sau $infinit$ daca nu. Apoi facem o parcurgere de la $2$ la $M$ si zicem $x[j] = min {x[j], x[j - 1] + 1}$. Apoi facem o parcurgere de la $M - 1$ la $1$ si recalculam $x[j] = min {x[j], x[j + 1] + 1}$. Astfel, simulam o plimbare pe segmentul $i - 1$.

Acum, nu ne mai ramane de facut decat sa notam ca $d[i][j] = y[j]$ daca $X[i] ≤ j ≤ Y[i]$, sau $infinit$ daca nu.

De observat ca aceste calcule pot fi facute cu un singur sir $d[1...M]$, nefiind nevoie nici de tabloul bidimensional $d$, nici de $x$ sau $y$.

De observat ca aceste calcule pot fi facute cu un singur sir $d[1...M]$, nefiind nevoie nici de tabloul bidimensional $d$, nici de $x$ sau $y$.
 
+Observatie+: Solutia nu se foloseste de faptul ca $A{~i~} ≤ A{~i+1~}$. Acest detaliu este unul care sa simplifice vizualizarea panzei de paianjen