Cod sursa(job #983152)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 10 august 2013 23:04:09
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<cstdio>
#include<vector>
using namespace std;
int a[5005];
int d[5005];
int p[5005];
int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    int ind,n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=n;i>=1;i--)
    {
        ind=-1;p[i]=-1;d[i]=1000000;
        for(int j=i+1;j<=n;j++)
            if(a[i]<=a[j])
            {
                if(ind==-1 || a[ind]>a[j])
                    ind=j;
                if(d[i]>d[ind]+1 || (d[i]==d[ind]+1 && a[ind]<a[p[i]]))
                {
                    d[i]=d[ind]+1;
                    p[i]=ind;
                }
            }
        if(d[i]==1000000)
            d[i]=1;
    }
    ind=1;int elem_min=a[1];
    for(int i=2;i<=n;i++)
        if(a[i]<elem_min)
        {
            elem_min=a[i];
            if(d[i]<d[ind] || (d[i]==d[ind] && a[i]<a[ind]))
                ind=i;
        }
    printf("%d\n",d[ind]);
    while(ind!=-1)
    {
        printf("%d ",ind);
        ind=p[ind];
    }
    return 0;
}