Cod sursa(job #1147967)

Utilizator PatrikStepan Patrik Patrik Data 20 martie 2014 12:22:13
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
    #include<cstdio>
    using namespace std;
    #define NMAX 5001
    int N , v[NMAX] , d[NMAX] , poz[NMAX] , maxx , minn , best ,p ;
    bool u[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] );
        u[N]  = 1;
        maxx = v[N];
        for(int i = N-1 ; i ; i-- )
            if(v[i] >= maxx)
        {
            maxx = v[i];
            u[i]  = 1;
        }
        for(int i = 1 ; i <= N ; ++i )
        {
            best = 0;
            for(int j = 1 ; j < i; ++j )
                if(v[j] <= v[i] && ( (d[j] == best && v[j] < v[poz[i]]) || d[j] > best) )
            {
                best = d[j];
                poz[i] = j;
            }
            d[i] = best +1 ;
        }
        minn = N+1;
        for(int i = 1 ; i<= N ; ++i )
            if(u[i] && minn > d[i])
            {
                minn = d[i];
                p =i;
            }
        printf("%d\n" , minn);
        tipar(p);
        return 0;
    }

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