Cod sursa(job #168863)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 31 martie 2008 20:33:12
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#define inf 1000000000

long n,i,j,a[5005],l[5005],t[5005],min,max;
long mark[5005],p,lmin,valmin;

int main(){
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);
    
    scanf("%ld",&n);
    for (i=1;i<=n;i++)
        scanf("%ld",&a[i]);
    
    l[n]=1;
    t[n]=0;
    for (i=n-1;i;i--){
        //
        min=inf;
        lmin=n+1;

        p=0;
        for (j=i+1;j<=n;j++)
            if (a[j]>=a[i]){
               if (a[j]<min){
                  min=a[j];
                  if (l[j]<lmin){lmin=l[j];valmin=a[j];p=j;}
                  else if (l[j]==lmin)
                          if (a[j]<valmin){valmin=a[j];p=j;}
               }
               mark[j]=1;
            }
        if (p){
          l[i]=lmin+1;t[i]=p;
        }
        else {t[i]=0;l[i]=1;}
    }
    /*
    for (i=1;i<=n;i++)
        printf("%ld ",l[i]);
    printf("\n");
    for (i=1;i<=n;i++)
        printf("%ld ",mark[i]);
    printf("\n");
    for (i=1;i<=n;i++)
        printf("%ld ",t[i]);
    printf("\n");
    */
    min=n+1;
    for (i=1;i<=n;i++)
        if (!mark[i]){
           if (l[i]<min){min=l[i];p=i;}
           else if (l[i]==min&&a[i]<a[p])p=i;
        }
    printf("%ld\n",min);

    while (p){
          printf("%ld ",p);
          p=t[p];
    }      

    printf("\n");

return 0;
}