[Runda 26] - Wyścigi Futerkowych Zaprzęgów

ďťż

Przemysław Derengowski - 3 maja 2010, o 15:27
" />Czy ktoś mógłby opisać poprawne rozwiązanie? Z tego co widziałem, to nikt nie dostał za to zadanie 10 pts., jednak może ktoś ma poprawny algorytm, ale zrobił np. drobny błąd w implementacji? Jak nikt nie będzie wiedział jak to rozwiązać, to co wtedy? Jakieś wskazówki od autora? Podejrzewam, że to jakiś dynamik, bo zachłanny dostał 2x WA.

Anna Piekarska - 4 maja 2010, o 18:29
" />Zapomniałam dopisać warunek na dwie kolejne pary... Już jest AC. Tak, to jest dynamik.
Załóżmy, że w pewien sposób wiemy jak rozłożone są rasy chomików w zaprzęgu i chcemy tylko dopasować dostępne chomiki tych ras. Wśród optymalnych rozwiązań jest to, w którym siły chomików od początku zaprzęgu są niemalejące. W takim razie posortuję sobie osobno obie rasy chomików i będę rozpatrywać tylko 2k najlepszych.
Rozpatrzę sobie takiego dynamika: stanem będzie (numer aktualnej pary, numer najsilniejszego nieużytego jeszcze chomika typu b, typ chomika w ostatniej parze po lewej, długość grupy chomików po lewej, typ chomika w ostatniej parze po prawej, długośc grupy chomików po prawej)
Zauważmy, że jeśli wiem ile było do tej pory par oraz ile było do tej pory chomików typu b, możemy łatwo w czasie stałym znaleźć liczbę chmoików typu c, więc nie musimy pamiętać tej liczby.
Przez długość grupy chomików rozumiemy długość najdłuższego łańcucha chomików tego samego typu kończącego się na ostatniej parze. Przykładowo dla zaprzęgu

Darmowy hosting zapewnia PRV.PL