Cod sursa(job #1148501)

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

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