Cod sursa(job #25907)

Utilizator pustiuRadu Zaharia pustiu Data 4 martie 2007 16:07:26
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<fstream.h>
int N, sol[5000], ant[5000];
long a[5000];
void citire ()
{
	ifstream f("subsir.in");
   f>>N;
   for(int i=1;i<=N;i++)
   	f>>a[i];
   f.close();
}

void dinamica ()
{
	sol[1]=1;
   ant[1]=-1;
   for(int i=2;i<=N;i++)
   {
   	long  max=0,maxj;
      for(int j=1;j<i;j++)
      	if (sol[j]>=max && a[j]<=a[i])
         	if (sol[j]==max && a[j]<=a[maxj])
            {
            	max=sol[j];
            	maxj=j;
         	}
            else
            {
            	max=sol[j];
               maxj=j;
            }
      if(max!=0)
      {
      	sol[i]=max+1;
         ant[i]=maxj;
      }
      else
      {
      	sol[i]=1;
         ant[i]=-1;
      }
   }
}

void afisare ()
{
	ofstream g("subsir.out");
   int max=0,x=1;
   for (int i=1;i<=N;i++)
   {
   	if(sol[i]>max)
      {
      	max=sol[i];
         x=i;
      }
      if (sol[i]==max && a[i]<a[x])
      {
      	max=sol[i];
         x=i;
      }
   }
   int solutie[1000],y=0;
   while (ant[x]!=-1)
	{
   	y++;
      solutie[y]=x;
      x=ant[x];
   }
   y++;
   solutie[y]=x;
   g<<y<<'\n';
   for(int k=y;k>=1;k--)
   	g<<solutie[k]<<' ';
   g.close();
}

int main ()
{
	citire();
   dinamica();
   afisare();
   return 0;
}