Obliczanie najdłuższego, rosnącego podciągu
Ostatnio zmodyfikowano 2011-12-27 23:19
matoł115 Temat założony przez niniejszego użytkownika |
Obliczanie najdłuższego, rosnącego podciągu » 2011-12-27 23:19:12 Witam! Tym razem mam napisać program liczący Najdłuższy podciąg rosnący Oto dokładna treść zadania: ZamekLimit czasowy: 8s, Limit pamięciowy: 32MB. Grasz w grę Zamek. W każdej turze możesz awansować swój zamek na pewien poziom i za każdy awans (nieważne o ile poziomów, ważne, że o co najmniej 1) dostajesz 1 punkt zwycięstwa. Udało ci się jednak podejrzeć pliki konfiguracyjne gry i wiesz, jakie będą kolejne poziomy, na które, w kolejnych turach, będzie można awansować zamek. Ponadto wiesz, że w $ k $-tej turze wykorzystanie możliwości awansu kosztuje $ 2^{k} $ dukatów. Policz więc, ile punktów zwycięstwa uda ci się zdobyć. Jeśli masz więcej możliwości, wybierz tę o najmniejszym koszcie. (Zauważ, że im wcześniej się zdecydujesz na awans, tym lepiej!). Zaczynasz od poziomu 0. Wejście W pierwszej linii wejścia znajdziesz ilość gier, które chcesz rozegrać. W każdej następnej znajduje się ilość tur $ n $ $ (n \leq 5*10^{5}) $, a następnie $ n $ liczb $ a_{i} $ $ (1\ \leq a_{i}\ \leq 10^{9}) $ określające na jaki poziom możesz awansować zamek w $ i $-tej turze. Wyjście Dla każdej gry wypisz jedną linię: niech zaczyna się od liczby $ m $ oznaczającej ilość punktów zwycięstwa, które możesz uzyskać, a następnie $ m $ liczb oznaczających kolejne poziomy (bez zerowego), które będziesz uzyskiwać, grając optymalnie. Przykład Dla danych wejściowych: 3 6 1 5 2 7 7 10 3 3 2 1 4 1 2 3 4
Poprawną odpowiedzią jest: 4 1 5 7 10 1 3 4 1 2 3 4 Wyjaśnienie: W pierwszym teście awansujemy kolejno: 0 -> 1 -> 5 -> 7 -> 10. Koszt takiego przedsięwzięcia to 2+4+16+64 = 86. W drugim możemy tylko raz awansować, więc robimy to najniższym kosztem = 2. W trzecim uda nam się zdobyć pełen komplet punktów. |
Oto mój program: #include <vector> #include <cstdio> using namespace std; int main() { int z, j, k; scanf( "%d", & z ); for( j = 0; j < z; j++ ) { int a, i, p, x, y, z, n = 0; scanf( "%d", & a ); vector < int > v[ a ]; for( i = 0; i < a; i++ ) { scanf( "%d", & p ); x = 0; y = i; while( x <= y ) { if( i == 0 ) { v[ 0 ].push_back( p ); n++; break; } else { z =( x + y ) / 2; if( v[ z ].size() == 0 ) { if( v[ z - 1 ].size() > 0 ) { if( v[ z - 1 ].back() < p ) { v[ z ].push_back( p ); n++; break; } else { y = z - 1; } } else { y = z - 1; } } else { if( v[ z ].back() < p ) { x = z + 1; } if( v[ z ].back() == p ) { break; } if( v[ z ].back() > p ) { if( z == 0 ) { v[ 0 ].push_back( p ); break; } if( z != 0 ) { if( v[ z - 1 ].back() < p ) { v[ z ].push_back( p ); } else { y = y - 1; } } } } } } } vector < int > wynik; p = v[ n - 1 ][ 0 ]; wynik.push_back( v[ n - 1 ][ 0 ] ); for( i = n - 1; i >= 0; i-- ) { x = 0; y = v[ i ].size() - 1; while( x <= y ) { z =( x + y ) / 2; if( v[ i ][ z ] < p ) { if( z == 0 ) { p = v[ i ][ z ]; wynik.push_back( p ); break; } else { if( v[ i ][ z - 1 ] > p ) { p = v[ i ][ z ]; wynik.push_back( p ); break; } else { y = z - 1; } } } if( v[ i ][ z ] >= p ) { x = z + 1; } } } printf( "%d ", wynik.size() ); for( i = wynik.size() - 1; i >= 0; i-- ) { printf( "%d ", wynik[ i ] ); } printf( "\n" ); } return 0; }
I wyniki: Test Wynik Czas Pamięć zam1.out accepted 0 ms 1004 zam2.out wrong answer 0 ms 1004 zam3.out accepted 0 ms 1004 zam4.out accepted 1899 ms 15500 zam5.out accepted 436 ms 31296
Czy ma ktoś pomysł co tutaj może być źle? Pozdrawiam |
|
« 1 » |