Fni triunghiular

[•blue_phoenix]

Buna!

In ultimul timp am incercat sa ma perfectionez in programarea dinamica citind diverse materiale de pe internet. Acum cateva zile am dat de o problema interesanta (din punctul meu de vedere). Am gasit-o intr-o culegere, la capitolul programare dinamica, dar, desi a fost data la un concurs, nu am putut gasi nimic legat de ea pe internet (mai putin cerinta, pe care am gasit-o aici: http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=691 ). Ma tot gandesc la ea de ceva timp, dar nu ma prind care sunt subproblemele....m-am gandit sa consider numai primele i linii din triunghi, sau subtriunghiuri echilaterale (dar dau peste recursivitate/subproblemele se suprapun:( si deci practic tot la bktr se reduce). Orice idee in legatura cu modul de definire a unei stari (si eventual si cu relatia de recurenta:D) e binevenita!^^

[•gabitzish1]

Trebuie sa rezolvi problema pt fiecare colt prin care poate intra hotul. Solutia va fi maximul dintre cele 3.

Recurenta ar fi ceva de genul

Cod:

d[nivel][camera] = s[nivel][camera] + max(d[nivel][camera - 1], d[nivel][camera + 1], d[nivel - 1][camera_de_deasupra])

dar trebuie sa tii cont si pe unde ai intrat intr'o camera, ca nu cumva sa iesi prin acelasi loc (nu e permis).

[•blue_phoenix]

Mersi de raspuns!

Dar nu inteleg 2 lucruri:
1) hotul poate intra prin orice triunghi care are cel putin o latura exterioara (nu doar prin varfuri);
cumva e demonstrabil/ cel putin evident de ce ar da optim daca intru printr-un varf si nu prin orice alt triunghi?
2) in relatia de recurenta... sunt doua tipuri de triunghiuri, cu varful in sus si cu varful in jos
deci: ultimul "parametru" al lui max este fie d[nivel - 1][camera_de_deasupra], fie d[nivel +1][camera_de_dedesubt], in functie de ce tip de triunghi e

apropo, d[nivel][camera]= suma maxima adunata stiind ca am considerat doar primele nivel niveluri si m-am oprit in camera camera? daca asta inseamna, e ca si cum as spune ca nu pot sa ma intorc prin triunghi (adica ar trebui sa merg doar intr-un sens, in jos; dar s-ar putea sa poti sa mergi in jos si apoi sa revi pe un nivelk superior din triunghi)
* in s[nivel][camera] tii datele de intrare, nu? s[1][1], s[2][1], s[2][2], s[2][3], s[3][1] etc.?

s-ar putea sa nu fi inteles eu bine cerinta, dar in datele de intrare din problema, cele de pe site, suma maxima nu e 110?
9+19+40+10+8+11+13

[•gabitzish1]

Un hot poate intra in cladire prin una dintre cele 3 incaperi care constituie varfurile triunghiului

Nu poate intra prin orice triunghi care are cel putin o latura exterioara.

d[nivel][camera]= suma maxima adunata stiind ca am considerat doar primele nivel niveluri si m-am oprit in camera camera

Corect!

Sensul in care mergi e in jos (cand treci pe nivelul urmator) si stanga sau dreapta cand te plimbi pe acelasi nivel. Sa revii pe un nivel superior nu poti, citeste mai bine cerinta!
Incearca sa rezolvi problema pt cazul in care hotul intra doar prin varful de sus al triunghiului (ce suma maxima poate obtine pana jos). Daca reusesti asta, pentru celelalte doua cazuri trebuie doar sa rotesti triunghiul.

[•blue_phoenix]

Da...scuze, ce am gasit pe net nu e chiar ce cerinta am gasit in culegere: Informatica de Emanuela Cerchez, ed Polirom:

Un "Fni" triunghiular este o cladire care are sectiunea in forma de triunghi echilateral, iar incaperile corespund unor triunghiuri echilaterale de latura 1. Pe fiecare latura a cladirii exista exact n incaperi. in fiecare incapere se gaseste cate un seif care contine o suma de bani.
Fiecare perete al incaperilor are o usa, initial deschisa, iar pe una din usile care comunica cu exteriorul in cladire poate intra un hot cu scopul de a "colecta" o suma catr mai mare de bani din seifurile existente in camere. Dupa intrarea in cladire, indiferent pe care usa exterioara, toate usile exterioare se inchid si nu mai pot fi deschise decat din interior, pentru a parasi cladirea. De asemenea, dupa parasirea unei incaperi din care au fost luati banii, toate cele trei usi ale acesteia se inchid automat si nu mai pot fi deschise.
Determinati suma maxima care poate fi colectata de hot si numarul de incaperi prin care trece hotul pentru a colecta suma respectiva.

Datele de intrare si desenul sunt aceleasi ca cele de pe site:)

[•devilkind]

@Gabitzish: Nu cred ca merge ce ai spus tu acolo. d[nivel][camera] depinde de d[nivel][camera + 1], iar d[nivel][camera + 1] depinde de d[nivel][camera] - avand astfel o dependenta circulara. Am impresia ca o sa primesti valori diferite in functie de cum parcurgi nivelul (daca parcurgi de la stanga la dreapta sau de la dreapta la stanga).

@Elena: Eu nu vad diferenta intre textul de pe campion si textul din culegere.

[•gabitzish1]

Restrictia care zice ca nu ai voie sa treci de 2 ori pe aceeasi usa cred ca ajuta in privinta asta. Doua camere invecinate pot depinde una de cealalta, si avem nevoie de cate o parcurgere si de la stanga la dreapta si de la dreapta la stanga pentru fiecare nivel, dar nu va fi nimic circular din cauza restrictiei.

Cred ca ar iesi ceva din ce am zis... sau poate ma insel rau si chiar nu imi dau seama.

[•blue_phoenix]

Mersi mult de post-uri!

Diferenta e ca in textul de pe campion hotul poate intra in cladire doar pe la varf, iar in textul din culegere, pe orice latura exterioara