317 Mall

[•DITzoneC]

Aici puteţi discuta despre problema Mall.

[•stef2n]

Solutia oficiala de la Mall mi se pare tare dubioasa.  Nu foloseste nici Li, nici Ei, nici Hi si nici Ci. Lipseste exact esentialul din dinamica aia.
Lasand la o parte aspectul asta, nu-mi dau seama ce e in neregula cu dinamica pe care o incerc eu, la care primesc WA Notez, intamplator exact ca in solutia oficiala, A[ i ][ j ]=castigul maxim care se poate obtine daca repartizez j muncitori primelor i firme. Pentru A[ i ][ j ] aleg maximul dintre cazurile urmatoare:
1. A[ i-1 ][ j ]     // nu trimit nici un muncitor la firma i
2. daca j>=Ci, A[ i-1 ][ j-Ci ] + Ei     // trimit exact Ci muncitori la firma i
3. A[ i-1 ][ j-k ] + Li , k variaza de la 1 la Ci-1     // trimit un numar k (<Ci) de muncitori la firma i
4. A[ i-1 ][ j-k ] + Hi, k variaza de la Ci+1 la j     // trimit un numar k (>Ci) de muncitori la firma i

Am facut vreo 4 implementari si tot 8 puncte iau. Chiar si pe implementarea O(N^3). E corecta dinamica?

[•astronomy]

Atentie, daca nu trimiti nici un muncitor la firma i trebuie sa aduni ceva (ori esti in cazul cu 0 < Ci sau 0 = Ci).

[•stef2n]

Multumesc! Intr-adevar asta era problema.
P.S. Solutia oficiala tot dubioasa ramane

[•cos_min]

A[i, j] = maxim(A[l, j-k]+Castig[l, k])

corect este a[i,j] = maxim(a[l,j-k] + castig[i,k] ) nu ?

[•alex_damian]

eu cred ca e castig [l,k];

dar daca sa zicem i = 10 si gasesc maxim pe pozitia l = 6. nu ar trebui sa adun si Li pentru 7, 8, 9, 10 ? ca ei primesc 0 ingrijitori.

sau nu am inteles eu bine rezolvarea ??

[edit] ce are testul 3? e mai special ??

[•fireatmyself]

corect este a[i,j] = maxim(a[l,j-k] + castig[i,k] ) nu ?

ai dreptate. am scris gresit un indice 

[edit] ce are testul 3? e mai special ??

nu are nimic special

[•alex_damian]

pfoaa... daca nu e special nu poate cineva sa il posteze aici ?? (n e mare ?? sau e sub 50 ? ) .. sau macar ceva asemanator

[•devilkind]

testele oficiale nu se fac publice

[•fireatmyself]

testele nu vor fi facute publice. daca te ajuta n = 69

[•pocaitu]

   Nu se poate uita cineva peste codul meu ? Primesc la toate testele Signal killed 11(SIGEGV) si numai nu pot gasi nici o eroare . Da, am citit articolul cu mesajele returnate de evaluator si tot nu am gasit nici o greseala .Ma chinui de o gramada la problema asta  
 http://infoarena.ro/utilizator/pocaitu?action=download&file=MA.CPP
 sau aici
 http://infoarena.ro/utilizator/pocaitu?action=download&file=malll.CPP

[•classius]

Imi da 96... WA la testu 5, poate sa imi dea cineva vreun caz particular care sa ma ajute sa imi observ greseala?