Cod sursa(job #458332)

Utilizator irene_mFMI Irina Iancu irene_m Data 24 mai 2010 16:01:27
Problema Subsir 2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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;
int uz[MaxN];

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], uz[j]=1;
                  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(!uz[i])
            {
                  if(lg[i]<min)
                        min=lg[i], pos=i;
                  else
                        if(lg[i]==min && a[i]<a[pos])
                              min=lg[i], pos=i;
            }

      printf("%d\n",min);
      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;
}