Cod sursa(job #872879)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 6 februarie 2013 18:00:55
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <fstream>
using namespace std;
const int N = 5001 ;
int n,R,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;
            }
        if(L[i]==N)
            L[i]=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;
}