Cod sursa(job #341001)

Utilizator DraStiKDragos Oprica DraStiK Data 17 august 2009 11:59:38
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>

#define DIM 5005

int a[DIM],best[DIM],urm[DIM],ok[DIM];
int n,nrmin,ind;

void read ()
{
    int i;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
        scanf ("%d",&a[i]);
}

void print (int val)
{
    printf ("%d ",val);
    if (urm[val]!=val)
        print (urm[val]);
}

void solve ()
{
    int i,j,imin,min,nmin;

    for (i=n; i>=1; --i)
    {
        for (ok[i]=best[i]=1,urm[i]=i, min=nmin=DIM, j=i+1; j<=n; ++j)
            if (a[j]>=a[i] && a[j]<nmin)
            {
                ok[j]=0;
                if (best[j]<min)
                {
                    min=best[j];
                    imin=j;
                }
                else if (best[j]==min && a[j]<a[imin])
                    imin=j;
                if (a[j]<nmin)
                    nmin=a[j];
            }
        if (min!=DIM)
        {
            best[i]=min+1;
            urm[i]=imin;
        }
    }
}

void show ()
{
    int i;

    for (nrmin=DIM, i=1; i<=n; ++i)
        if (ok[i])
            if (best[i]<nrmin)
            {
                nrmin=best[i];
                ind=i;
            }
	    else if (best[i]==nrmin && a[i]<a[ind])
                ind=i;
    printf ("%d\n",best[ind]);
    print (ind);
}

int main ()
{
    freopen ("subsir2.in","r",stdin);
    freopen ("subsir2.out","w",stdout);

    read ();
    solve ();
    show ();

    return 0;
}