Cod sursa(job #493948)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 20 octombrie 2010 02:19:11
Problema Subsir 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<cstdio>
int n,a[6000],lung[6000],next[6000];
void read()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
}
void df(int x)
{
    printf("%d ",x);
    if(next[x]!=-1)
        df(next[x]);
}
void solve()
{
    lung[n]=1;
    next[n]=-1;
    for(int i=n-1;i>=1;i--)
    {
        int min=1<<30,MIN=1<<30,pmin=0;
        for(int j=i+1;j<=n;j++)
            if(a[j]>=a[i])
            {
                if(a[j]<min)
                {
                    if(lung[j]<MIN)
                        MIN=lung[j], pmin=j;
                    else if(lung[j]==MIN && a[j]<a[pmin])
                        pmin=j;
                }
                if(a[j]<min)
                    min=a[j];
            }
        lung[i]=lung[pmin]+1;
        next[i]=pmin;
    }
    int MIN=1<<30,min=1<<30,pmin;
    for(int i=1;i<=n;i++)
    {
        if(lung[i]<MIN && a[i]<min)
            MIN=lung[i], pmin=i;
        if(lung[i]==MIN && a[i]<a[pmin])
            pmin=i;
        if(a[i]<min)
            min=a[i];
    }
    printf("%d\n",lung[pmin]);
    df(pmin);
}
int main()
{
    read();
    solve();
    return 0;
}