Probuje zrobic to zadanie https://pl.spoj.com/problems/MONFI/ niestety dostaje WA najpierw probowalem algorytmu zachlannego jednak po namysle doszedlem do wniosku ze nie bedzie dobry wiec znalazlem dynamika ktory powinien dzialac https://en.wikipedia.org/wiki/Activity_selection_problem#Weighted_activity_selection_problem
i teraz moje pytanie czy ja cos zle przepisalem jesli tak to dlaczego jesli nie to dlaczego dostaje WA wydawalo mi sie ze to powinna byc wzorcowka do zadania. Moze macie jakies podchwytliwe testy ktorych moj program https://ideone.com/9qTJ85 nie przechodzi.
W drugim teście odpowiedzią nie powinno być przypadkiem 99? 1-2 (2) + 4-5 (2) + 5-100 (95) = 99
Chyba nie poniewaz liczac w ten sposob w przykladzie testowym 4-6(3) + 8-12(5) = 8
Źle policzyłem… W każdym razie, wraz powinno być 97, nie 96. W tym algo przedziały nie muszą być przypadkiem posortowane według drugiego elementu?
przedzialy sortuje rysylalem tez druga wersje kodu ktora daje 97 w drugim przykladzie jednak tez dostalem wa
Udało mi się znaleźć taki test:
1 3 9 12 8 12 5 7
a widze blad sortowalem zly przedzial juz poprawilem https://ideone.com/47d4Cn poprawna odpowiedzia powinno byc 6
1 4 1 3 3 7 2 7 7 9
poprawna odpowiedz to 8.
Wielkie dzieki lordarab za bardzo dobry przyklad jest akceptacja. Dla potomnych trzeba bylo uzyc innego wyszukiwania binarnego wyszukujacego pierwszy wiekszy element