Cod sursa(job #1148519)

Utilizator PatrikStepan Patrik Patrik Data 20 martie 2014 20:53:44
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
    #include<cstdio>
    using namespace std;
    #define NMAX 5001
    #define INF 1000010
    int N , d[NMAX] , v[NMAX] , Dmin , Vmin , best , p , poz[NMAX];

    void tipar(int p);

    int main()
    {
        freopen("subsir2.in" , "r" , stdin );
        freopen("subsir2.out" , "w" , stdout );
        scanf("%d" , &N );
        for(int i = 1 ; i <= N ; ++i )
            scanf("%d" , &v[i]);
        d[N] = 1;
        for(int i = N-1 ; i ; i-- )
        {
            Vmin = Dmin = INF;
            for(int j = i+1 ; j<= N ; ++j )
            {
                if(v[j] >= Vmin || v[j] < v[i])continue;
                Vmin = v[j];
                if(Dmin >= d[j])
                {
                    Dmin = d[j];
                    poz[i] = j;
                }
            }
            if(Dmin == INF)d[i] = 1;
            else  d[i] = Dmin+1;
        }
        Vmin = Dmin = INF;
        for(int i = 1 ; i <= N ; ++i )
        {
            if(v[i] >= Vmin)continue;
            if(d[i] <= Dmin)
            {
                Dmin = d[i];
                p = i;
            }
            Vmin = v[i];
        }
        printf("%d\n" , Dmin);
        tipar(p);
        return 0;
    }

    void tipar(int p)
    {
        if(poz[p])
        {
            printf("%d " , p);
            tipar(poz[p]);
        }
        else printf("%d " , p);
    }