Cod sursa(job #458330)

Utilizator irene_mFMI Irina Iancu irene_m Data 24 mai 2010 15:50:58
Problema Subsir 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#define infile "subsir2.in"
#define outfile "subsir2.out"
#define MaxN 5024
#define Inf 1000024

int a[MaxN],lg[MaxN],poz[MaxN];
int N;

void read()
{
      int i;
      scanf("%d",&N);
      for(i=1;i<=N;i++)
            scanf("%d",&a[i]);
}

void solve()
{
      int i,j,min,jmin,val;

      poz[N]=0; lg[N]=1;

      for(i=N-1;i>=1;i--)
      {
            min=Inf; val=MaxN;

            for(j=i+1;j<=N;j++)
            {
                  if(a[i]<=a[j] && a[j]<=min && (lg[j]<val || (lg[j]==val && a[j]<a[jmin])))
                        jmin=j, val=lg[j];
                  if(a[j]>=a[i] && a[j]<min)
                        min=a[j];
            }

            if(val<MaxN)
                  lg[i]=val+1, poz[i]=jmin;
            else
                  lg[i]=1, poz[i]=0;
      }
}

void write()
{
      int i,min=Inf,valmin=Inf,pos=N+10;
      for(i=1;i<=N;i++)
      {
            /*if((lg[i]<valmin || (lg[i]==valmin && a[i]<a[pos])) && a[i]<min)
                  valmin=lg[i], pos=i;
            if(a[i]<min)
                  min=a[i];*/
            if(a[i]<valmin)
                  valmin=a[i], pos=i;
      }

      printf("%d\n",lg[pos]);
      while(lg[pos])
      {
            printf("%d ",pos);
            pos=poz[pos];
      }
}
int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      read();
      solve();
      write();

      fclose(stdin);
      fclose(stdout);
      return 0;
}