Cod sursa(job #4867)

Utilizator crawlerPuni Andrei Paul crawler Data 8 ianuarie 2007 15:55:31
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>

long n, i, j, v[5002], x[5001], p[5001], a[5001], tmp, max;

int main()
{
  freopen("subsir2.in", "r", stdin);
  freopen("subsir2.out", "w", stdout);

  scanf("%ld\n", &n);

  for(i=1;i<=n;++i)
   scanf("%ld", &v[i]);

  for(i=n;i>0;--i)
   {
    x[i]=1;
    p[i]=i;
    
    for(j=i+1;j<=n;++j)
     if(v[i]<=v[j])
      if(!a[j])
       {
        a[j]=1;
        if((p[i]!=i && v[j]<=v[p[i]]) || p[i]==i)
          {
           x[i]=x[j]+1;
           p[i]=j;
          }
       }
   }


  max=1;
  
  for(i=2;i<=n;++i)
   if(!a[i] && x[i]<x[max])
    max=i;


  for(i=1;i<=n;++i)
   if(x[i]==max && v[i]<=v[max])
    max=i;

  printf("%ld\n",tmp=max);
  for(i=1;i<=x[max];++i)
   {
    printf("%ld ",tmp);
    tmp=p[tmp];
   }

  
   
  return 0;
}