Thread: [ODD] Rozwiązanie

Mógłby ktoś pochwalić się swoim poprawnym swoim rozwiązaniem?
Kluczem do rozwiązania jest zastanowienie się jakby wyglądał wydajny algorytm sprawdzający, czy dany ciąg jest dobry.
Oczywiste obserwacje są takie że zawsze można ścinać drzewa od lewej do prawej i że nie opłaca się mieć >=2 dni kiedy pierwsze drzewa są takich samych gatunków. W owym wydajnym algorytmie sprawdzającym czy ustalony ciąg jest poprawny chcemy iść od lewej do prawej i trzymać zbiór gatunków drzew, które mogły otwierać dzień, w którym scielismy i-te drzewo. Jeżeli przyjdzie nam jakieś drzewo którego gatunek mógł otwierać aktualny dzień, to wiemy że aktualny moment jest potencjalnym zamykającym dzień i następujące po nim drzewo będzie mogło otwierac dzień. Oczywiste z danego zbioru nigdy nic nie wylatuje.
Mając to zrozumienie, łatwo już je przekształcić na dynamika rozwiązującego oryginalne zadanie w n^2. dp[i][j][k] (gdzie 1<=i<=n, 1<=j<=i, k-bool) będzie oznaczać ile jest takich ciągów że pierwsze i drzew tworzy taki ciąg, że dany "otwierający zbiór" ma rozmiar j, gdzie i-ty dzień mógł lub nie mógł zamykać jakiś dzień w zależności od wartości boolowskiej zmiennej k
Dzięki za wyjaśnienie.