Plan de atac (probleme-candidat):
1. http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en

Reducerea complexitatii, transformarea problemei intr-un de contruire a unui arbore binar.
 

2. http://code.google.com/codejam/contest/dashboard?c=32001#s=p0&a=3

3. http://code.google.com/codejam/contest/dashboard?c=32001#s=p3&a=3

4. http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1

5. http://code.google.com/codejam/contest/dashboard?c=32010#s=p3&a=3
h2. Sugestii Silviu

h3. Exemplu:

Pentru secvenţa de numere $(8 24 12 6)$, răspunsul ar fi $(9, -2, 1, 7, 8)$.

Pentru secvenţa de numere $(8 24 12 6)$, răspunsul ar fi $42$. Astfel, se testează mai întâi poziţia $2$. Dacă nu este proastă, mai rămâne de testat poziţia $1$. Altfel, în cel mai rău caz mai trebuie testate poziţiile $3$ şi $4$, aducând timpul total la $24 + 12 + 6 = 42$.

h3. Rezolvare:

O să începem prin a da altă îmbrăcăminte problemei. Astfel, să ne imaginăm că am construi un arbore binar de căutare pe şirul dat, având drept chei poziţiile din şir, şi drept valori auxiliare valorile poziţiilor respective din şir (un nod cu cheia $i$ va avea valoarea auxiliara $a{~i~}$.
Acum, există mulţi arbori binari de căutare posibile pentru şirul iniţial. Totuşi, să presupunem că am construit unul. Atunci, strategia noastra de testare a elementelor din şir se va desfăşura conforma arborelui. Astfel, testăm mai întâi în poziţia din rădăcină. Dacă poziţia respectivă este proastă, ne ducem în fiul drept. Altfel, mergem in fiul stâng. În ambele cazuri se reia procedeul. Căutarea se termină cand nu mai putem merge într-un fiu.
 
Acum, să observăm că dacă considerăm costul unui drum în arbore să fie suma

h2. Programare dinamica folosind bitmask