Cod sursa(job #5107)

Utilizator crawlerPuni Andrei Paul crawler Data 10 ianuarie 2007 16:40:44
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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(((p[i]!=i)?v[j]<=v[p[i]]:1)&& v[j]>=v[i])
      {
       p[i]=j;
       x[i]=x[j]+1;
      }
       
/*    tmp=i+1;
    
    for(j=i+1;j<=n;++j)
     if(v[i]<=v[j])
      if(!a[j])
       {
        a[j]=1;
        if(x[j]<x[tmp])
         tmp=j;
       }

    for(j=i+1;j<=n;++j)
     if(x[j]==x[tmp])
      if(a[j]<=1)
       {
        if(v[j]>=v[i])
         a[j]=2;
        if(v[j]<v[tmp])
         tmp=j;
       }

       

     if(!p[i])
      {
       p[i]=tmp;
       x[i]=x[tmp]+1;
      }*/
   }


  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;
}