Cod sursa(job #1006675)

Utilizator gbi250Gabriela Moldovan gbi250 Data 7 octombrie 2013 16:01:30
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <cstdio>

using namespace std;

int i, j, n, pos, MIN, v[5001], len_max[5001], next_el[5001];
bool ok[5001];

int main()
{
    freopen("subsir2.in", "r", stdin);
    freopen("subsir2.out", "w", stdout);
    scanf("%d", &n);
    for(i=1; i<=n; ++i)
    {
        scanf("%d", &v[i]);
        len_max[i] = 1;
    }

    for(i=n-1; i>=1; --i)
    {
        MIN = 0x3f3f3f3f;
        for(j=i+1; j<=n; ++j)
            if( v[j] >= v[i] )
            {
                ok[j] = 1;
                if( v[j] < MIN)
                {
                    MIN = v[j];

                    if( len_max[j] + 1 > len_max[i] )
                    {
                        len_max[i] = len_max[j] + 1;
                        next_el[i] = j;
                    }
                    else if( len_max[j] + 1 == len_max[i] && v[ next_el[i] ] > v[j] )
                        ok[j] = 1,
                        next_el[i] = j;
                }
            }
    }

    pos=1;
    for(i=2; i<=n; ++i)
        if( !ok[i] )
            if(len_max[i] < len_max[pos] || ( len_max[i] == len_max[pos] && v[i] < v[pos] ) )
                pos=i;

    printf("%d\n", len_max[pos]);

    while( pos )
    {
        printf("%d ", pos);
        pos = next_el[pos];
    }
    return 0;
}