Padurari
O primă observaţie aproape evidentă este că pădurarii vor alege mereu copaci consecutivi. Pornind de la această observaţie se poate construi un algoritm trivial bazat pe programare dinamică având complexitatea O(N*K) şi care ar fi obţinut 20 de puncte.
Pentru a ajunge la un algoritm eficient, o abordare posibilă este să modelăm problema ca un graf. Nodurile vor fi reprezentate de copaci, iar muchiile de posibilităţile de alegere ale pădurarilor. Astfel, va exista muchie între două noduri dacă şi numai dacă acestea sunt consecutive. Se observa uşor ca acest graf este unul bipartit. Problema se reduce acum la găsirea unui cuplaj de cardinal K si cost minim în graful construit. Daca studiem modul de comportare al algoritmului pentru determinarea cuplajului de cost minim pe acest graf, se observă ca o muchie de întoarcere va fi folosită doar în cazul în care dorim să selectăm ulterior cele două muchii vecine. Folosind această observaţie, putem prevedea comportarea algoritmului în acest pas, înlocuind muchia de întoarcere ce ar trebui introdusă şi cele două muchii vecine, cu o nouă muchie ca in desenul următor:
Acum se poate construi un nou algoritm care selectează la fiecare din cei K pasi muchia minimă din graf si face transformările necesare. Inserările şi ştergerile muchiilor se pot face în timp logaritmic folosind un heap, astfel algoritmul având complexitatea O(K*logN).
Există un caz particular ce trebuie tratat cu atenţie. Când muchia aleasă este prima sau ultima din graf, abordarea de mai sus nu funcţionează. Totuşi, în acest caz este uşor de observat că va fi mereu de preferat să alegem această muchie în locul vecinei, deoarece are costul mai mic şi nu crează restricţii asupra altor muchii din graf.
