Cod sursa(job #984788)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 15 august 2013 14:29:07
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<stdio.h>
int v[5004];
unsigned f[5004],l[5004];
int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    int x;
    unsigned j,i,n,m;
    scanf("%u",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(i=n;i>=1;i--)
    {
        m=f[i]=0;
        l[i]=1000005;
        for(j=i+1;j<=n;j++)
            if(v[i]<=v[j])
            {
                if(m==0 || v[m]>v[j])
                    m=j;
                if(l[i]>l[m]+1 || (l[i]==l[m]+1 && v[m]<v[f[i]]))
                {
                    l[i]=l[m]+1;
                    f[i]=m;
                }
            }
        if(l[i]==1000005)
            l[i]=1;
    }
    m=1;
    x=v[1];
    for(i=2;i<=n;i++)
     if(v[i]<x)
        {
            x=v[i];
            if(l[i]<l[m] || (l[i]==l[m] && v[i]<v[m]))
                m=i;
        }
    printf("%u\n",l[m]);
    while(m!=0)
    {
        printf("%u ",m);
        m=f[m];
    }
    return 0;
}