Kombinatoryczne programowanie dynamiczne, zadanie "Nawiasy"

pytanie zadane 2 grudnia 2020 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
edycja 2 grudnia 2020 przez wojtek_suchy

Mam takie zadanie:
Działanie odejmowania nie jest łączne, np.(5−2)−1 = 2, natomiast 5−(2−1) = 4, a zatem (5−2)−1 = 5−(2−1). Wynika stąd, że wartość wyrażenia postaci 5−2−1zależy od kolejności wykonywania odejmowań. Zwykle przy braku nawiasów przyjmuje się, że wykonujemy działania wkolejności od lewej do prawej, czyli wyrażenie 5−2−1 jest równoważne wyrażeniu (5−2)−1. Mamy dane wyrażenie postaci:x1±x2±···±xn gdzie ± oznacza +(plus) lub−(minus), ax1, x2,···, xn oznaczają (parami) różne zmienne. Chcemy w wyrażeniu postaci:x1−x2−···−xn tak rozstawić n−1 par nawiasów, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu. Na przykład, chcąc uzyskać wyrażenie rów-noważne wyrażeniu:x1−x2−x3+x4+x5−x6+x7 możemy w:x1−x2−x3−x4−x5−x6−x7 rozmieścić nawiasy w następujący sposób:(((x1−x2)−((x3−x4)−x5))−(x6−x7))
Uwaga: Interesują nas tylko wyrażenia w pełni i poprawnie ponawiasowane. Wyrażeniem w pełnii poprawnie ponawiasowanym jest
•pojedyncza zmienna,
•wyrażenie postaci(w1−w2), w którym w1 i w2 to w pełni i poprawnie ponawiasowane wyrażenia. Nieformanie mowiąc, nie interesują nas wyrażenia, w których występują na przykład konstrukcjepostaci:(),(xi),((···))lubx1−(x2−x3).
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita n, (2 <= 5000).Jest to liczba zmiennych w danym wyrażeniu. W każdym z kolejnychn−1wierszy jest zapisanyjeden znak,+lub−. Wi-tym wierszu zapisany jest znak występujący w danym wyrażeniu międzyxi−1axi.
Wyjście
Twój program powinien zapisać w pierwszym wierszu standardowego wyjścia jedną liczbę całkowitąrówną ilości różnych sposobów (modulo109), na jakie można rozstawićn−1par nawiasów wwyrażeniux1−x2−···−xntak, aby jednoznacznie określić kolejność wykonywania odejmowań ijednocześnie uzyskać wyrażenie równoważne danemu.
PrzykładDla danych wejściowych:
7

-
+
+

+

poprawnym wynikiem jest:3
I nie mam kompletnie pomysłu jak do tego podejść, czy moglibyście mi jakoś pomóc ? :D

komentarz 2 grudnia 2020 przez tkz Nałogowiec (42,000 p.)

Wklej treść...

komentarz 2 grudnia 2020 przez wojtek_suchy Mądrala (6,880 p.)

Przepraszam, zapomniałem że do niektórych zadań trzeba się logować

komentarz 2 grudnia 2020 przez Whistleroosh Maniak (56,980 p.)

To zadanie jest całkiem trudne. Ono jest z finału OI. Ja sam go nie umiem rozwiązać na 100. Mogę ewentualnie powiedzieć jak mniej więcej wygląda rozwiązanie w O(n^3)