Cod sursa(job #49113)

Utilizator the_andyAndrei Stefan the_andy Data 5 aprilie 2007 12:54:07
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>
#define NMAX 5000

int main(void)
{
int V[NMAX];
long int A[NMAX];
int T[NMAX];
int n;
int i,j;
int pmin;
int amin;
long max,min;
FILE *f;

//citeste datele de intarare
f=fopen("subsir2.in","rt");
fscanf(f,"%d",&n);
for(i=0;i<n;i++)
  fscanf(f,"%ld",&A[i]);
fclose(f);

//face programare dinamica
V[n-1]=1;
T[n-1]=-1;

for(i=n-2;i>=0;i--)
  {
  //cauta cel mai lung subsir la care poate adauga elementul A[i]
  max=0;
  min=A[i+1];
  amin=1000001;
  for(j=i+1;j<n;j++)
    {

    if(A[j]>A[i])
      if(((A[i]<min)&&(A[j]<min))||(i+1==j))
      if(V[j]+1>max)
	{
	max=V[j]+1;
	pmin=j;
	amin=A[j];
	} else
	if(V[j]+1==max)
	  if(A[j]<amin)
	  {
	  pmin=j;
	  amin=A[j];
	  }

    if(A[j]<min)
     min=A[j]; //memoreaza valoarea minima de pana acuma
    }

  if(max!=0)
  {
    V[i]=max;
    T[i]=pmin;
  } else
  {
    V[i]=1;
    T[i]=-1;
  }
}  

//afiseaza solutia
f=fopen("subsir2.out","wt");
fprintf(f,"%d\n",V[0]);
i=0;
while(i!=-1)
  {
  fprintf(f,"%d ",i+1);
  i=T[i];
  }
fprintf(f,"\n");
fclose(f);

//sf
return 0;
};