Clasa a VII-a lecția 33 - 16 apr 2020

Tema - rezolvări

Rafturi

Problema rafturi a fost dată la ONI 2009 clasa a 9^a. Este o problemă tipică de programare dinamică. Ea cere să urcăm cît mai puține trepte pe o scară astfel încît să culegem toate cărțile, știind că putem culege cărți nu doar din dulapul curent, ci și din dulapurile de alături, stînga și dreapta.

Exemplu

Să analizăm exemplul din enunț. Observăm că dacă avem mai multe cărți pe aceeași coloană (același dulap) doar cartea de la înălțime maximă contează. Drept care exemplul din enunț poate fi văzut ca un șir de înălțimi maximale:

Număr dulap	1	2	3	4	5	6
Înălțime	1	0	8	0	4	2

Este destul de ușor de văzut că putem grupa înălțimile 8 și 4, mergînd la înălțime 8. Vom culege separat înălțimile rămase, 1 și 2. Totalul minim este, deci, 11.

Exemplu

Să executăm manual exemplul din enunț:

Număr dulap i	1	2	3	4	5	6
Înălțime h[i]	1	0	8	0	4	2
Suma minimă smin[i]	1	1	8	8	9	11

Bila2

Problema bila2 este o problemă destul de tipică de calcul a numărului de drumuri.

Rezolvări aici [1].

Lecție - concurs (de acasă)

Concurs clasa a 7^a

• bomboane4
• clasa0

Temă

Problemele au fost adăugate la tema 33.

Rezolvări aici [2].