Cod sursa(job #3259403)

Utilizator monica_LMonica monica_L Data 26 noiembrie 2024 10:49:37
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#define inf 1000000
#define dim 5005
using namespace std;

ifstream f("subsir2.in");
ofstream g("subsir2.out");

int n, k, A[dim], L[dim], T[dim], ok[dim];

void citire()
{
    int i, min=inf;

    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>A[i];
        if( A[i] < min )
        {
            min = A[i];
            ok[i] = 1;
        }
    }
}

void Solve()
{
    int i, j, mn, best=inf, vmin=inf;

    for(i=n; i>=1; --i)
    {
        L[i] = mn = inf;
        for(j=i+1; j<=n; ++j)
            if( A[j] >= A[i] && A[j] < mn )
            {
                mn = A[j];
                if( L[j]+1 < L[i] )
                {
                    L[i] = L[j]+1;
                    T[i] = j;
                }
                else if( L[j]+1 == L[i] && A[j] < A[T[i]] )
                    T[i] = j;
            }

        if( !T[i] ) L[i] = 1;

        if( ok[i])
           if( L[i] < best || L[i] == best && A[i] < vmin )
            {
                best = L[i];
                vmin = A[i];
                k = i;
            }
    }
}

void afis()
{
    g<<L[k]<<'\n';

    while( k )
    {
        g << k << " ";
        k = T[k];
    }

}

int main()
{
    citire();
    Solve();
    afis();

    return 0;
}