Salut!
Eu am facut problema asta in doua moduri (facut adica da raspunsul corect, dar ia tle pe 7 teste din 10, in ambele moduri)
Am notat cu l1 numarul de laturi de tip 1 vandute pana acum (catete verticale), l2 numarul de laturi de tip 2 (catete orizontale)
si l3 numarul de laturi de tip trei (ipotenuze)
Primul e brut:
fac doua foruri in care fixez l1 si l2 (l3 se deduce, este k-l1-l2). am trei functii:
suma1(l1,l2,l3), suma2(l1,l2,l3) si suma3(l1,l2,l3) care calc. valoare parcelei de tip 1 (respectiv 2, 3), stiind ca am vandut deja l2 si l3 laturi de tipul l2 si resp l3; sursa e aici
http://infoarena.ro/job_detail/636657?action=view-sourceA doua solutie am incercat sa o fac o parcurgere in latime; mie mi s-a parut o solutie mai buna ca prima, dar, desi tot doar trei teste intra in timp, ea ia chiar mai mult
initial am in coada nodul (0,0,0,0) cu semnif ca la sf zilei 0, am vandut 0 laturi l1, 0 laturi l2 si castigul este 0 (pe l3 nu e nevoie sa-l tin, se deduce, este (ziua-l-l2))
expandarea nodului (ziua,l1,l2,castig) duce la adaugarea in coada a inca trei noduri:
(ziua+1,l1,l2,castig+suma3(l1,l2,ziua-l1-l2+1)) daca vand latura 3,
(ziua+1,l1+1,l2,castig+suma1(l1+1,l2,ziua-l1-l2)) daca vand latura 1,
(ziua+1,l1,l2+1,castig+suma2(l1,l2+1,ziua-l1-l2)) daca vand latura 2. expandez pana la generatia k, inclusiv.
din tot ce am pus vreodata in coada aleg maximul, dpdv al castigului.
mi s-a parut o sol mai buna ca prima, pt ca chem functiile de suma de mai putine ori decat in primul caz...
sursa e aici:
http://infoarena.ro/job_detail/637095?action=view-sourceImi poate spune cineva, pe scrut, care era ideea? sumele pe bucati oricum trebuiesc calculate,nu? si ele iau mult timp...