Answer these queries
23.02.2010 - Tomasz Górzny
GSS2Dla porządku:
Przykład: A = 4 -2 -2 3 -1 zapytanie (1,5) - val( 4, -2, -2, 3 ) = 4-2+3 = 5 Pora na ostatni i najtrudniejszy problem, czyli GSS2. Treść zadania jest prawie taka sama, jak pierwszego. Różnica polega na tym, że liczymy sumę różnych elementów. Największym błędem przy rozwiązywaniu jest za mocne sugerowanie się poprzednimi zadaniami. Tak naprawdę rozwiązuje się je podobnie, ale zupełnie inaczej. Na wstępie zauważmy, że możemy zapomnieć o sumach prefiksowych, bo problem nie ma takiej ładnej struktury. Zapominamy. Oznaczanie powtórzeńZaczniemy od tego, że dla każdej pozycji wyznaczymy ostatni wcześniejszy indeks, pod którym znajduje się taka sama wartość (albo 0, jeżeli to pierwsze wystąpienie). Wartości ciągu A są małe, więc można (ale nie trzeba) zrobić to liniowo, w taki sposób:
Liczymy val(A[1]..A[N])Powiedzmy, że zapytanie jest jedno i szukana jest tylko wartość sumy. Postępujemy oczywiście tak, że dodajemy do siebie wartości z tych indeksów, które mają poprzednika ustawionego na 0. To było za proste :). Ogólnie, dla zapytania (a,b) uwzględnimy tylko pola z poprzednikami mniejszymi od a (bo pozostałe już policzyliśmy).
Komplikujemy - maksimum dla ustalonego jednego końcaSkomplikujmy: początek jest ustalony i trzeba znaleźć maksimum po końcach. Zapamiętujemy więc po drodze max z kolejnych wartości. Skomplikowaliśmy.
Zamiast początku ustalmy koniec. Oczywiście zrobimy tak, że po prostu policzymy od końca (tzn odwracamy i liczymy normalnie). Nic przełomowego... Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
(4 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com