1. http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en
Reducerea complexitatii, transformarea problemei intr-una de construire a unui arbore binar.

Alo Alo Andrane
 

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

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, pe care îl considerăm de acum ca fixat. 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 de la rădăcină la o frunză ca suma valorilor auxiliare din drumul (unic) respectiv, atunci se observă că costul strategiei bazate pe acest arbore este chiar costul maxim al unui drum ! De acum încolo, vom defini costul unui arbore ca costul maxim al unui drum din el. Să exemplificăm pe şirul din exemplu:

Acum, să observăm că dacă considerăm costul unui drum în arbore de la rădăcină la o frunză să fie suma valorilor auxiliare din drumul (unic) respectiv, atunci se observă că costul strategiei bazate pe acest arbore este chiar costul maxim al unui drum ! Să exemplificăm pe şirul din exemplu:

Se observă că costul maxim al unui drum este $42$, minim posibil, exact ca răspunsul din exemplu.
Deci, am redus problema la construirea unui arbore binar de căutare, care are costul minim.

Se observă că cel mai lung

Acum devine clară o primă soluţie folosind programarea dinamică. Astfel, să presupunem că notăm cu $opt[i][j]$ costul minim al unui arbore construit pe cheile $(i, i + 1, ..., j)$. Fie $r[i][j]$
poziţia rădăcinii arborelui cu costul minim. În cazul existenţei mai multor rădăcini posibile, se alege cea mai din stânga.

h2. Programare dinamica folosind bitmask