Jak rozwiązaliście zadanie?
Patrząc po rankingu nie było ono wcale takie trudne, ale mi się nie udało nawet bruta wykminić. :(

Załóżmy, że będziemy to zadanie robić na odwrót. Zamiast szukać najmniejszej liczby połączeń, będziemy zaczynać ze wszystkimi połączeniami i zastanowimy się ile możemy usunąć. Żadna różnica, tylko wygodniej mi się tak myślało. Więc zrobimy sobie dp.
Dp[i] - największa ilość połączeń które można usunąć, z i-tym włącznie(!!). Więc zróbmy to najpierw w O(n^2). Chcemy policzyć dp[i], przeiterujmy się po wszystkich mniejszych j, stwierdzając, że tam będzie poprzednie cięcie. Ale musi też zostać spełniony warunek, że suma na przedziale od j+1 do i będzie nieujemna. Więc chcemy wybrać tylko takie j które to spełniają, i wziąć maksimum z ich wartości dp. W ten oto sposób mamy O(n^2). No to teraz wiemy już, że braliśmy wartość tylko z tych punktów, że spełniony był ten warunek o nieujemnej sumie. Jak go szybko sprawdzić. Niech pref to tablica sum prefiksowych. Żeby j oraz i mogły być kolejnymi cięciami, to pref[i] - pref[j] >= 0, czyli pref[i] >= pref[j]. Dobra, możemy zatem posortować sobie po wartości sumy prefiksowej rosnąco. Iterując się teraz w naszej nowej kolejności dalej liczymy to samo dp. Teraz nie musimy się martwić o to, że wyjdzie przedział z ujemną sumą. Jedynie chcemy brać teraz maximum po wszystkich dp które miały mniejszy indeks od i, a to da się w prosty sposób robić na jakimś drzewie przedziałowym maxów. W ten sposób dostajemy O(n*log(n)). Liczę, że da się coś zrozumieć :)

Równoważne będzie znalezienie najdłuższego niemalejącego podciągu sum prefiksowych, który zawiera pref[0] i pref[n] :)

Obiekty będziemy przeglądać od lewej do prawej.

Dla każdego obiektu 'i' będziemy przechowywać listę potencjalnych projektów sieci energetycznej obejmujących obiekty 0..i. Dla kolejnego obiektu 'i+1' będziemy konstruować taką listę bazując na liście dla obiektu 'i'.

Każdy projekt będzie zakładał, że obiekty od 0 do 'i' są podzielone na autonomiczne energetycznie obszary (spójne składowe sieci). Oczywiście każdy taki obszar musi mieć nieujemny bilans energetyczny. Wyjątkiem jest skrajny prawy obszar (kończący się w obiekcie 'i') - on może zostać rozszerzony do obszaru 'i+1' (lub jeszcze dalej) - dlatego ten obszar może mieć ujemny bilans energetyczny.

W projekcie istotne dla nas będą dwa atrybuty: 'power' oraz 'cost'. Ten drugi to oczywiście koszt, który musimy ponieść aby zrealizować projekt. Z kolei 'power' to bilans energetyczny tego skrajnie prawego obszaru sieci. Nie musimy znać szczegółów na temat zamkniętych obszarów sieci (tych położonych na lewo od ostatniego - niedomkniętego obszaru) - istotne jest tylko to, że koszt ich realizacji jest zagregowany w zmiennej 'cost'.

W jaki sposób sporządzić listę projektów dla obiektu 'i+1'? Mamy dwie możliwości:
- budujemy połączenie od 'i' do 'i+1',
- nie budujemy tego połączenia.

W tym pierwszym przypadku każdy projekt z listy 'i' musimy przenieść na listę 'i+1' uwzględniając poprawki dla planowanego połączenia od 'i' do 'i+1'. A zatem projekt (p, c) przechodzi na (p + data[i+1], c + dist(i, i+1)).

W drugim przypadku odcinamy ostatni obszar sieci i otwieramy nowy obszar. Co do zamykanego właśnie obszaru sieci mamy tylko jedno wymaganie: aby bilans energetyczny był nieujemny. Dlatego w tym miejscu z listy projektów dla 'i' wybieramy najtańszy z nieujemnym 'power'. Do listy projektów dla 'i+1' dodajemy wpis (data[i+1], choosenCost). Oznacza on, że nowo otwarty obszar ma bilans data[i+i], a koszt choosenCost to po prostu koszt realizacji domknięcia poprzedniego obszaru.
Oczywiście drugi przypadek nie zawsze jest możliwy - może się bowiem zdarzyć, że na liście projektów dla 'i' wszystkie projekty mają power < 0.

Po przejrzeniu wszystkich obiektów z listy projektów dla ostatniego wybieramy najtańszy z nieujemnym bilansem.

Algorytm działa O(n*n) - bo dla każdego obiektu przepisujemy całą listę projektów, która w każdym kroku może zostać rozszerzone o jeden element.

O usprawnieniach w kolejnym poście...

Usprawnienia:

W trakcie wykonywania operacji na liście projektów możemy eliminować projekty gorsze (nielepsze) od innych.

Na przykład dwa projekty: (p1, c1) i (p2, c2) - jeśli p1 <= p2 oraz c1 >= c2 to widzimy, że pierwszy projekt jest gorszy od drugiego (nie dość, że droższy, to jeszcze daje mniejszy bilans energetyczny). A zatem (p1, c1) można usunąć.

To gwarantuje nam, że lista projektów będzie zawierała uporządkowane wpisy (pi, ci), takie że p1 < p2 < p3 < ... oraz c1 < c2 < c3 < ...

Listę projektów przechowywałem w 'map<int, int>' (power jako klucz).

Kolejne usprawnienie dotyczy przepisywania obiektów z jednej listy do drugiej z modyfikacją parametrów. Ponieważ modyfikacja parametrów jest taka sama dla wszystkich projektów, to można zrobić sobie globalne modyfikatory, np:

int deltaPower, deltaCost;

Wtedy wpis w mapie (pi, ci) traktujemy jako (pi + deltaPower, ci + deltaCost).
I zamiast przepisywać wszystkie wpisy zmieniając o (data[i+1], dist(i, i+1)), wystarczy zmodyfikować deltaPower i deltaCost.

Ponadto wyszukiwanie najtańszego nieujemnego projektu możemy zrobić wyszukiwaniem binarnym (a konkretnie lower_bound)

Przy takiej implementacji listy projektów w każdym kroku wykonujemy pojedyncze operacje (wliczając operacje na mapie: lower_bound oraz insert), stąd ostateczna złożoność całego algorytmu to O(n*logn)

Ja zrobiłem tak:

1. Jeśli suma wszystkich a_i < 0 to nie ma rozwiązania.

2. Jeśli ta suma = 0, to jest tylko jedna możliwość sieci - tam gdzie jest przepływ zerowy nie trzeba robić połączenia.

3. Jeśli suma > 0, to można wybrać miejsca gdzie zmniejszymy a_i tak aby zmaksymalizować odcinki o przepływie zerowym i aby suma całkowita była 0.

4. Przepływ na odcinku między i a i+1 możemy regulować w zakresie od suma a_{1..i} do suma a_{i+1..n}, jeśli w tym przedziale nie ma zera to na pewno nie uda się tu zrobić przerwy w sieci.

5. Reasumując szukamy takiego ciągu dla 1..n niemalejącego od 0 do suma który by przechodził przez maksymalną ilość punktów gdzie możemy zrobić przerwę.

6. Algorytm Dijkstry na grafie wszystkich możliwych wykresów ciągów dał się dobrze zoptymalizować. Przebiegałem od 1..n pamiętając na multisecie ile razy ciąg zaliczył miejsca zerowego przepływu na danym poziomie 0...suma. Jeśli zaliczyłem nowe miejsce, to kasuję 1 następny większy element.

7. Liczba n minus ilość elementów multiseta daje odpowiedź. Koszt O(n log n).