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?