Cod sursa(job #393174)

Utilizator DastasIonescu Vlad Dastas Data 8 februarie 2010 23:33:05
Problema Subsir 2 Scor 61
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>

FILE *in = fopen("subsir2.in","r"), *out = fopen("subsir2.out","w");

const int maxn = 5001;

int n, a[maxn], l[maxn], p[maxn], ok[maxn];

void read()
{
    fscanf(in, "%d", &n);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%d", a + i);
}

void go()
{
    l[n] = 1;
    l[0] = 1 << 30;

    int sol = l[0], psol;
    for ( int i = n - 1; i; --i )
    {
        l[i] = 1;
        p[i] = 0;

        // l[j] minim
        int pmin = 0, min = l[0];
        for ( int j = i + 1; j <= n; ++j )
        {
            if ( a[j] > a[i] )
            {
                if ( a[j] <= min )
                {
                    min = a[j];
                    if ( l[j] <= l[pmin] )
                        pmin = j;
                }

                ok[j] = 1;
            }
        }
        if ( !pmin )
            continue;

        l[i] = l[pmin] + 1;
        p[i] = pmin;
    }

    //printf("%d\n", p[1]);

    int maxx = l[0];
    for ( int i = 1; i <= n; ++i )
    {
        if ( !ok[i] )
            if ( l[i] < sol || (l[i] == sol && a[i] < maxx) )
            {
                sol = l[i];
                psol = i;
                maxx = a[i];
            }

       // printf("%d %d %d %d %d\n", i, l[i], ok[i], a[i], p[i]);
    }
    fprintf(out, "%d\n", sol);

    for ( int i = psol; i; i = p[i] )
        fprintf(out, "%d ", i);
}

int main()
{
    read();

    go();

    return 0;
}