Cod sursa(job #982857)

Utilizator thewildnathNathan Wildenberg thewildnath Data 10 august 2013 13:11:19
Problema Subsir 2 Scor 63
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>

int v[5002],a[5002],t[5002],f[5002];

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

int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    int n,i,j,m,sol,s;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
    for(i=1;i<=n;++i)
    {
        m=-2000000000;
        a[i]=2000000000;
        for(j=i-1;j>0;--j)
        {

            if(v[j]<v[i])
            {
                if(v[j]>m&&(a[j]<a[i]-1||(a[j]==a[i]-1&&v[j]<v[t[i]])))
                {
                    t[i]=j;
                    f[j]=i;
                    a[i]=a[j]+1;
                }
                if(f[j]==0)
                    f[j]=i;
            }
            if(v[j]>m&&v[j]<v[i])
                m=v[j];

        }
        if(a[i]==2000000000)
                a[i]=1;
    }
    sol=s=2000000000;
    for(i=1;i<=n;++i)
        if(f[i]==0&&(a[i]<sol||(a[i]==sol&&v[i]<v[s])))
        {
            s=i;
            sol=a[i];
        }
    /*for(i=1;i<=n;++i)
        printf("%2d ",a[i]);printf("\n");
    for(i=1;i<=n;++i)
        printf("%2d ",t[i]);printf("\n");
    for(i=1;i<=n;++i)
        printf("%2d ",f[i]);printf("\n");
    printf("\n");*/
    printf("%d\n",sol);
    afis(s);
    printf("\n");
    return 0;
}