infoarena

Aici puteti discuta despre problema Expozitie (http://infoarena.ro/problema/expozitie).

Imi explica cineva solutia oficiala de dinamica va rog ? Nu e explicata deloc relatia aia de recurenta, doar trantita acolo in document, ca sa nu mai zic de aia cu combinatorica.Merci :fighting:

Relația de recurență este explicată, dar probabil nu foarte explicit....
Ideea e că tu ai (i,j) = în câte feluri poți aranja pe i scânduri, oricare din primele j tipuri de desene. Tipurile vor fi puse în ordine crescătoare, deoarece 1 2 2 3 este același cu 3 2 2 1.
Acum să vedem cum obținem (i,j). Ideea e că ne bazăm pe soluția cu i-1 scânduri. Pe scândura i trebuie să punem tabloul j, tablou ce îl putem pune după oricare tip din tablourile 1,2,...,j. Deci tabloul j poate fi pus după tabloul 1 la (i-1,1), după tabloul 2 la (i-1,2), după tabloul j la (i-1,j).
Deci (i,j) = (i-1,1) + (i-1,2) + ... + (i-1,j).
Dar noi știm că (i-1,1) + (i-1,2) + ... + (i-1,j-1) este (i,j-1) (a fost calculat la coloana anterioară de pe aceeași linie). De aici rezultă că (i,j) = (i,j-1) + (i-1,j).

Deci (i,j) = (i-1,1) + (i-1,2) + ... + (i-1,j).

de ce nu e (i-1,j) = (i-1,1) + (i-1,2) + ... + (i-1,j) ?

Sau de fapt nu mai conteaza, ultimul element de pe scandura i ? La fel este nr de moduri? conteaza doar modurile de la primele i-1 aranjari? Ultimul tablou este oricum >= decat celelalte si nr de moduri este acelasi ?

Păi exact, iar acum când vrei să calculezi D[ i ][ j ], încerci să pui pe scândura i desenul j. De aceea, numărul de posibilități de a pune desenul j pe scândura i este egal cu D[ i-1 ][1] + D[ i-1][2] + ... +D[ i-1 ][j], mai precis tu pui desenul j "după" desenele 1, 2, 3, ..., j.

Am formula, stiu cazurile particulare... Ce fac mai departe??? A incercat cineva sa-mi explice care o facuse de 100, dar  si-a batut joc de mine in mod sigur.. Merge rezolvarea cu un for de la i la n si apoi un for de la j la d, si sa calculez D[j]..pt ca iau 30 puncte cu rezolvarea asta si vad ca exista si numere mari.Cum fac ? Ma folosesc de cazurile particulare si folosesc un tablou tridimensional?

Nu cred ca raspunsurile care le-ai primit au fost bataie de joc, mai mult, din cate vad eu baietii au explicat destul de clar solutia problemei (ceea ce nu se face in deobste pe forum  :) ). Ar fi bine sa citesti mai atent enuntul / explicatiile si sa te straduiesti sa intelegi anumite detalii. Sunt sigur ca daca o sa te chinui un pic vei obtine 100p. Si pe viitor posteaza mai concis, daca ceri raspunsul la peste 3 intrebari simultan cel mai probabil nu o sa ti se raspunda la nici una  :).

Cate posibilitati exista pentru o scandura si mai mult de 2 tipuri de desene? 0 sau d? :?

Daca n < d*k raspunsul este 0

Imi explica si mie cineva care ar fi problema cu testele 6 si 8 ca nu prea imi dau seama de ce iau wa!!! ms!!