Cod sursa(job #983294)

Utilizator thewildnathNathan Wildenberg thewildnath Data 11 august 2013 14:33:40
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>

int v[5002],t[5002],l[5002];

void afis(int i)
{
    printf("%d ",i);
    if(t[i])
        afis(t[i]);
}

int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    int n,i,j,k,m;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
    for(i=n;i>=1;--i)
    {
        k=-1;
        l[i]=2000000000;
        for(j=i+1;j<=n;++j)
        {
            if(v[i]<v[j])
            {
                if(k==-1||v[k]>v[j])
                    k=j;
                if(l[i]>l[k]+1||(l[i]==l[k]+1&&v[k]<v[t[i]]))
                {
                    l[i]=l[k]+1;
                    t[i]=k;
                }
            }
        }
        if(l[i]==2000000000)
            l[i]=1;
    }
    k=1;
    m=v[1];
    for(i=2;i<=n;++i)
    {
        if(v[i]<m)
        {
            m=v[i];
            if(l[i]<l[k]||(l[i]==l[k]&&v[i]<v[k]))
                k=i;
        }
    }
    printf("%d\n",l[k]);
    afis(k);
    printf("\n");
    return 0;
}