Cod sursa(job #198575)

Utilizator DastasIonescu Vlad Dastas Data 12 iulie 2008 18:07:16
Problema Subsir 2 Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 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]);
}

void go()
{
    for ( int i = n; i; --i )
    {
        b[i] = 1;

        int pmin = 0;
        int min = inf;
        for ( int j = i + 1; j <= n; ++j )
            if ( a[i] <= a[j] )
            {
                if ( a[j] < min )
                    min = a[j], pmin = j;
                else if ( a[j] == min )
                    if ( b[j] < b[pmin] )
                        pmin = j;
            }

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

    int min = inf, pmin = 0;

    for ( int i = 1; i <= n; ++i )
        if ( a[i] < min )
            min = a[i], pmin = i;

    fprintf(out, "%d\n", b[pmin]);
    while ( pmin )
    {
        fprintf(out, "%d ", pmin);
        pmin = p[pmin];
    }
}

int main()
{
    read();

    go();

    return 0;
}