Zadanie Kolejka SPOJ

pytanie zadane 31 maja 2016 w C i C++ przez Hohlik741 Nowicjusz (160 p.)

Rozwiązuje zadanie na SPOJ, tutaj link: http://pl.spoj.com/problems/AL_01_02/

Nie mam już pomysłów jak przyśpieszyć program, cały czas wypluwa o przekroczonym czasie ... Bardzo proszę was o pomoc, może ktoś mnie naprowadzi na sprytniejsze rozwiązanie.

Tutaj mój kod, który wydaje mi się teraz najszybszy:

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int n;
    cin>>n;
    for(int g=0; g<n; g++)
    {
        string pom;
        char kolej[1000000];
        int dl;
        cin>>kolej;
        dl=strlen(kolej);
        pom=kolej[dl-1];
        for(int i=dl-2; i>=0; i--)
        {
            if(kolej[dl-1]>kolej[i])
            {
                continue;
            }
            else
            {
                char znak;
                znak=kolej[dl-1];
                pom=znak+pom;
            }
            dl=i+1;
            if(dl==1)
            {
                char znak;
                znak=kolej[dl-1];
                pom=znak+pom;
            }
        }
        cout<<pom<<endl;
        }
        return 0;

}

2 odpowiedzi

odpowiedź 23 czerwca 2016 przez p0m0 Obywatel (1,190 p.)

Jest to zadanie na najdłuższy podciąg rosnący. Radzę poczytać:
http://informatyka.wroc.pl/node/402?page=0,3

komentarz 23 czerwca 2016 przez CharlieGG Użytkownik (900 p.)

Nie to nie jest zadanie na najdłuższy podciąg rosnący ;)

komentarz 23 czerwca 2016 przez p0m0 Obywatel (1,190 p.)

Jak to nie? Treść zadania można by podać tak:
dostaniesz t ciągów znaków. Wypisz najdłuższy podciąg niemalejący z każdego z nich

komentarz 23 czerwca 2016 przez CharlieGG Użytkownik (900 p.)

W takim razie czemu dla pierwszego testu przykładowego odpowiedź to "n", a nie np. "kkn", albo "kkkn"? (w zależności czy szukamy spójnego czy nie).

komentarz 23 czerwca 2016 przez p0m0 Obywatel (1,190 p.)
edycja 23 czerwca 2016 przez p0m0

Zgadzam się. Popełniłem błąd. Przepraszam.

komentarz 23 czerwca 2016 przez Hohlik741 Nowicjusz (160 p.)

No niestety, gdyby to był najdłuższy podciąg rosnący to raczej problemów by nie było... Ktoś ma jakieś inne pomysły ?

komentarz 24 czerwca 2016 przez p0m0 Obywatel (1,190 p.)

Do rozwiązania zadania potrzeba złożoności liniowej do każdego przykładu, ale to daje TLE. Wydaje mi się, że trzeba użyć innej biblioteki niż iostream, albo innego języka niż c++

komentarz 24 czerwca 2016 przez CharlieGG Użytkownik (900 p.)

Zajrzyj w najlepsze wysyłki. Prawie wszyscy zrobili to w C++, więc nie mów że nie można używając C++ :) Sam zrobiłem to w tym języku, więc się da. Co prawda iostream niekoniecznie wystarczy, ale jeśli zamienimy cout na putchar to spokojnie wejdzie.