Czy zadanie można rozwiązać w czasie wielomianowym?

0

Nie pytam o to jak rozwiązać, tylko chcę się upewnić czy na pewno można znaleźć optymalne rozwiązanie w wielomianowym czasie.

title

0

Abstrahując kompletnie od problemu, w zadaniach algorytmicznych które są automatycznie oceniane, złożoność można zwykle wywnioskować na podstawie rozmiaru danych wejściowych i spodziewanego wyniku. Zwykle jak nie istnieje wielomianowy algorytm to również jest podawana funkcja oceny jak daleko od idealnego rozwiązania jest to rozwiązanie które daje nasz algorytm.

Podsumowując tutaj masz co najwyżej n log n, a zapewne liniowo się da.

0

Na oko wygląda na dynamik. Robisz dp[i][s] gdzie i to index od 0 do n-1, s oznacza stan zajęcia i-tej kolumny, a wartość dp oznacza maksymalną liczbę skoczków rozstawioną na planszy do i-tej kolumny włącznie, tak, że i-ta kolumna jest w stanie s. Dla s mamy 8 możliwości, są to wszystkie możliwe podzbiory i-tej kolumny (interpretowane jako: kolumna jest pusta, w górnym wierszu jest skoczek, w środkowym wierszu jest skoczek, w dolnym wierszu jest skoczek, w pierwszych dwóch wierszach jest skoczek i tak dalej). Następnie stan [i+2][s] uzależniamy od stanów [i][s] zgodnie z ruchami skoczka, czyli przykładowo dp[i+2][5] oznacza, że chcemy dać skoczki w górnym i dolnym wierszu kolumny i+2, a żeby tak móc zrobić, w kolumnie i nie może być skoczka w środkowym wierszu kolumny (bo wtedy atakowalibyśmy górny i dolny wiersz kolumny i+2). Czyli dp[i+2][5] = max(dp[i][0], dp[i][1], dp[i][3], dp[i][5]) + 2, czyli maksimum z (pusta kolumna, skoczek tylko w górnym wierszu, skoczek tylko w dolnym wierszu, skoczek w górnym i dolnym wierszu) + 2 (bo dokładamy skoczki w górnym i dolnym wierszu kolumny). Uwzględnienie pól zakazanych jest proste, bo w polu zakazanym nie dodamy skoczka (czyli przepisujemy wartość), a z pola zakazanego nie zaatakuje nas żaden skoczek (czyli możemy go dorzucić do maksimum).

Złożoność to O(sn).

Przyjąłem, że plansza jest szersza niż dłuższa, a dopiero po napisaniu zorientowałem się, że zadanko rysuje ją inaczej, ale to nie jest istotne koncepcyjnie.
Ponadto trzeba umieć odtworzyć skoczki, ale to już jest względnie proste po wygenerowaniu całej tablicy, trzeba oprócz wartości liczbowej spamiętywać, którą dokładnie wartością z funkcji maksimum ją wyliczyliśmy.

1 użytkowników online, w tym zalogowanych: 0, gości: 1