Cod sursa(job #872866)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 6 februarie 2013 17:54:03
Problema Subsir 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb

#include <cstdio>
#include <fstream>

using namespace std;

const int N = 5001 ;

int n,R;
int A[N],P[N],L[N];
bool C[N];

void READ ()
{

    ifstream in ("subsir2.in");

    in>>n;

    for( int i=1 ; i<=n ; ++i )
    {
        in>>A[i];
        L[i]=N;
    }

}

void SOLVE ()
{

    L[n]=1;

    for( int i=n-1 ; i ; --i )
    {
        int V=1<<30;
        for( int j=i+1 ; j<=n ; ++j )
            if( A[i] <= A[j] )
            {
                if( A[j] < V )
                {
                    if( L[j]+1 < L[i] )
                    {
                        L[i]=L[j]+1;
                        P[i]=j;
                    }
                    else
                        if( L[j]+1 == L[i] && A[j] < A[P[i]] )
                            P[i]=j;
                    V=A[j];
                }
                C[j]=1;
            }
    }

    int V,Lm=N;
    for( int i=1 ; i<=n ; ++i )
    {
        if( C[i] )
            continue;
        if( L[i] < Lm )
        {
            Lm=L[i];
            V=A[i];
            R=i;
        }
        else
            if( L[i] == Lm && A[i] < V )
            {
                V=A[i];
                R=i;
            }
    }

}

void OUT ()
{

    freopen ("subsir2.out","w",stdout);

    printf("%d\n",L[R]);

    for( ; R ; R=P[R] )
        printf("%d ",R);

}

int main ()
{

    READ ();
    SOLVE ();
    OUT ();

    return 0;
}