• Infoarena Monthly 2014
• Format
• Clasament
• Organizatori
• Sponsori si premii
• Regulament
•  
• Runda 1
• Runda 2
• Runda 3
• Runda 4
• Runda 5
• Runda 6
• Runda 7
• Runda 8
• Runda 9
• Runda 10
• Runda 11
• Runda 12

Spargere2

Vom reţine un vector auxiliar cu următoarea semnificaţie:

• d[i] = suma maximă ce poate fi obţinută folosind primele i seifuri

Vom parcurge seifurile de la 1 la N, iar pentru fiecare seif i, avem câteva opţiuni:

• Deschid seiful i şi le ignor pe cele de dinainte.
• Deschid seiful i şi iau şi suma maximă obţinută prin folosirea primelor i - k seifuri.
• Nu deschid seiful i, deci iau suma maximă obţinută prin folosirea celor dinaintea sa, primelor i - 1 seifuri.

În concluzie, vom avea:

• d[i] = max( v[i], d[i - k] + v[i], d[i - 1] )

Rezultatul se găseşte în d[n].