Cod sursa(job #198345)

Utilizator DastasIonescu Vlad Dastas Data 10 iulie 2008 14:24:06
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>

const int maxn = 5001;
const int inf = 1 << 29;

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

int n;
int a[maxn];

int b[maxn];
int p[maxn];

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

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

int go()
{
    int max = -inf;

    for ( int i = 1; i <= n; ++i )
    {
        b[i] = 1;

        int min = inf;
        for ( int j = 1; j < i; ++j )
            if ( b[j] + 1 > b[i] && a[j] < a[i] )
                min = a[j], p[i] = j, b[i] = b[j] + 1;
//            else if ( b[j] + 1 == b[i] && a[j] <= a[i] )
//                if ( a[j] < min )
//                    min = a[j], p[i] = j;

        if ( b[i] > max )
            max = b[i];
    }

    return max;
}

void print(int t)
{
    if ( !t )
        return;

    print(p[t]);
    fprintf(out, "%d ", t);
}

int main()
{
    read();

    int max = go();
    fprintf(out, "%d\n", max);

    int min = inf, pmin = 0;

    for ( int i = 1; i <= n; ++i )
        if ( b[i] == max )
            pmin = i;

    print(pmin);

    return 0;
}