Cod sursa(job #342491)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 22 august 2009 00:30:19
Problema Subsir 2 Scor 42
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>

#define Nmax 5100
#define Inf 0x3f3f3f3f


int V[Nmax],N,max,p,poz[Nmax],best[Nmax],i,j,min;


void read_data()
{
  freopen("subsir2.in","r",stdin);
  scanf("%d\n", &N);
  for (i=1;i<=N;++i)
  scanf("%d ", &V[i]);
}


void find_max()
{
  best[N]=1;
  poz[N]=-1;
  max=0;
  p=N;
  min=Inf;
  for (i=N-1;i>=1;--i)
       {
	best[i]=1;
	poz[i]=-1;
	//if (V[i]<=min)
		//min=V[i];
	for (j=i+1;j<=N;++j)
	     {
	       if (V[i]<V[j] && best[i]<best[j]+1 && V[j]<min)
		   {
		    best[i]=best[j]+1;
		    poz[i]=j;
			min=V[j];
		    if (best[i]>max)
			{
			 max=best[i];
			 p=i;
			}
		   }
	      }
     }
}

void constr_sir()
{
	int j,ok;
   i=p;
   while (i!=-1)
   {
	   ok=1;
   //printf("%d ", V[i]);
	   for (j=1;j<=N && ok;++j)
		    if (V[i]==V[j])
			{
				printf("%d ", j);
				//break;
				ok=0;
			}
			
   i=poz[i];
   }
	
	
}


void write_data()
{
  freopen("subsir2.out","w",stdout);
  printf("%d\n", max);
}

int main()
{
   read_data();
   find_max();
   write_data();
   constr_sir();
   return 0;
}