h3. (problema grea, clasele 11-12)

Problema se rezolva folosind metoda programarii dinamice, dar

Problema se rezolva folosind metoda programarii dinamice. Ca prim pas vom precalcula niste informatii pentru fiecare culoar care vor fi folosite apoi in algoritmul de programare dinamica. Astfel pentru un culoar $i$ exista 4 scenarii care ne intereseaza:
* se face un pas de distanta $D$ din coltul de sus al unui culoar adiacent la coltul de sus al culoarului $i$, se iau toate produsele de pe culoar incepand de sus si se revine la coltul de jos al culoarului $i$
* se face un pas de distanta $D$ din coltul de sus al unui culoar adiacent la coltul de sus al culoarului $i$, se iau toate produsele de pe culoar incepand de sus si se revine la coltul de sus al culoarului $i$
* se face un pas de distanta $D$ din coltul de jos al unui culoar adiacent la coltul de jos al culoarului $i$, se iau toate produsele de pe culoar incepand de jos si se revine la coltul de jos al culoarului $i$
* se face un pas de distanta $D$ din coltul de jos al unui culoar adiacent la coltul de jos al culoarului $i$, se iau primele $k$ produse de pe culoar incepand de jos si se revine la coltul de jos al culoarului $i$, se face un pas de distanta $D$ din coltul de sos al unui culoar adiacent la coltul de sos al culoarului $i$, se ia restul de produse de pe culoar incepand de sus si se revine la coltul de sus al culoarului $i$
 
Se observa ca primul tip de scenariu (cat si cel simetric) are mereu un cost constant, si anume $D+M+1$. Asadar, se vor precalcula informatii doar pentru ultimele 3 tipuri. Aceste informatii se pot calcula usor sortand produsele de pe fiecare culoar si parcurgandu-le (in cazul ultimului scenariu). Complexitatea acestui pas este $O(P*lgP + N)$.
Vom realiza acum algoritmul de programare dinamica construind traseul optim culoar cu culoar, de la $1$ la $N$. Se observa ca exista $6$ stari care ne intereseaza la un culoar $i$:
 
* $0$ - costul unui traseul optim care trece prin coltul de sus al culoarului $i$, fara a trece prin coltul de jos al culoarului $i$
* $1$ - costul unui traseul optim care trece prin coltul de sus al culoarului $i$, care trece prin coltul de jos al culoarului $i$, iar traseul este conex
* $2$ - costul unui traseul optim care trece prin coltul de sus al culoarului $i$, care trece prin coltul de jos al culoarului $i$, iar traseul *nu* este conex, adica este format din doua trasee care se vor uni la un moment dat (la un culoar $> i$)
* $3$ - costul unui traseul optim care trece prin coltul de jos al culoarului $i$, fara a trece prin coltul de sus al culoarului $i$
* $4$ - costul unui traseul optim care trece prin coltul de jos al culoarului $i$, care trece prin coltul de sus al culoarului $i$, iar traseul este conex
* $5$ - costul unui traseul optim care trece prin coltul de jos al culoarului $i$, care trece prin coltul de sus al culoarului $i$, iar traseul *nu* este conex, adica este format din doua trasee care se vor uni la un moment dat (la un culoar $> i$)
 
Pentru a calcula oricare din cele $6$ stari ne uitam la cele $6$ stari ale culoarului $i-1$. In total, vor exista $6*6 = 36$ de tranzitii; fiecare se poate calcula in $O(1)$ folosind informatiile precalculate la primul pas. Cele $36$ de tranzitii se pot determina usor pe foaie, trasand cateva exemple. Complexitatea acestui pas este $O(N)$, deci rezolvare este in final $O(P*lg P + N)$.

==Include(page="template/preoni-2007/footer")==