Heavy metal
O solutie care ar fi obtinut aproximativ 40 de puncte ar fi putut fi urmatoarea: ne construim un vector Best[i], reprezentand timpul total maxim in care vor canta formatii daca fiecare concert se va termina inainte de ora i. Rezultatul cautat se va afla in Best[Tmax], unde Tmax va fi timpul maxim de terminare a unui concert. Relatia de recurenta va fi:
pentru i de la 1 la Tmax
Best[i] = Best[i-1];
pentru fiecare concert j cu B[j] = i
Best[i] = max(Best[i], Best[A[j]] + (B[j] - A[j]))Solutia ce ar fi obtinut punctajul maxim nu reprezinta nimic altceva decat o rafinare a acestui algoritm. Observam ca valorile A[i] si B[i] sunt foarte mari, iar pentru a rezolva aceasta problema le vom normaliza. Vom sorta intervalele in functie de timpul de terminare si vom calcula Best[i] doar pentru valorile in care exista cel putin un concert care se termina la timpul i.
