Cod sursa(job #17441)

Utilizator mariusdrgdragus marius mariusdrg Data 15 februarie 2007 21:24:56
Problema Subsir 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<stdio.h>

const int maxn = 10001;


const int inf = 100000000;
int a[maxn];
int i;
int n;
int min;
int la[maxn];
int le[maxn];
int poz;
int j;


int main()
{
        freopen("subsir2.in","r",stdin);
        freopen("subsir2.out","w",stdout);
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
                scanf("%d",&a[i]);
                a[i]+=1000001;
        }
        for(j=n;j>=1;j--)
        {
                le[j]=inf;
                la[j]=0;
                min=inf;
                for(i=j+1;i<=n;i++)
                {
                        if (a[i]<min&&a[i]>=a[j]) min=a[i];
                        if (min==a[i]&&a[i]>=a[j]&&(le[i]+1<le[j]||(le[i]+1==le[j]&&a[la[j]]>a[i])))
                        {
                                le[j]=le[i]+1;
                                la[j]=i;
                        }
                }
                if (le[j]==inf) le[j]=1;
        }
        min=inf;
        int min1=inf;
        poz=inf;
        for(i=1;i<=n;i++)
        {
                if (a[i]<min1) min1=a[i];
                if (a[i]==min1&&(le[i]<min||(a[poz]>a[i]&&le[i]==min)))
                {
                        min=le[i];
                        poz=i;
                }
        }
        printf("%d\n",le[poz]);
        while(poz)
        {
                printf("%d ",poz);
                poz=la[poz];
        }
        return 0;

}