Cod sursa(job #1006745)

Utilizator gbi250Gabriela Moldovan gbi250 Data 7 octombrie 2013 17:54:21
Problema Subsir 2 Scor 77
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 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[n] = 1;
    for(i=n-1; i>=1; --i)
    {
        len_max[i] = 0x3f3f3f3f;

        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] )
                        next_el[i] = j;
                }
            }
        if( len_max[i] == 0x3f3f3f3f)
            len_max[i] = 1;
    }

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

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

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