Împărțim șirul în k subsecvențe consecutive. Cerința 1 (maxim cel mai mare raft): celelalte k-1 rafturi sunt singletoni de la capete, deci răspuns = total - min(prefix(a)+sufix(b)). Cerința 2 (maxim cel mai mic raft): căutare binară pe prag, verificată cu un greedy.
Vezi enunțul oficialÎncearcă întâi singur! Indiciile elimină din satisfacția rezolvării.
Avem un șir de pietricele cu valori și îl tăiem în exact bucăți consecutive (rafturi). Fiecare tăietură decide cât pune fiecare raft. Cele două cerințe par să ceară lucruri opuse, dar amândouă se sprijină pe aceeași unealtă: sumele de prefix. Cu ele, valoarea oricărui raft de la poziția la e doar o scădere: , calculată instant.
Conectează-te ca să marchezi problemele rezolvate.