Cod sursa(job #1006935)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 7 octombrie 2013 22:08:15
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 5005;
const int oo = 0x3f3f3f3f;

int N;
int V[Nmax];
int D[Nmax], T[Nmax];
int solution = oo, index;

void read()
{
    freopen("subsir2.in", "r", stdin);

    scanf("%d", &N);

    for ( int i = 1; i <= N; ++i )
            scanf("%d", &V[i]);

    fclose( stdin );
}

void solve()
{
    for ( int i = N; i >= 1; i-- )
    {
        D[i] = oo;

        int minim = -1;

        for ( int j = i + 1; j <= N; ++j )
        {
            if ( V[i] <= V[j] )
            {
                if ( minim == -1 || V[j] < V[minim] )
                        minim = j;

                if ( minim != -1 && ( D[minim] + 1 < D[i] || ( D[minim] + 1 == D[i] && V[minim] < V[ T[i] ] ) ) )
                {
                    D[i] = D[minim] + 1;
                    T[i] = minim;
                }
            }
        }

        if ( D[i] == oo )
                D[i] = 1;
    }

    int minim = -oo;

    for ( int i = 1; i <= N; ++i )
    {
        if ( minim == -oo || V[minim] > V[i] )
                minim = i;

        if ( minim == i && ( solution > D[i] || ( solution == D[i] && V[i] < V[index] ) ) )
        {
            solution = D[i];
            index = i;
        }
    }
}

void print()
{
    freopen("subsir2.out", "w", stdout);

    printf("%d\n", solution);

    while ( index != 0 )
    {
        printf("%d ", index);
        index = T[index];
    }

    fclose( stdout );
}

int main()
{
    read();
    solve();
    print();

    return 0;
}