Cod sursa(job #287009)

Utilizator andrei_vs2009Cozma Andrei andrei_vs2009 Data 24 martie 2009 13:58:40
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<fstream>

using namespace std;

int n, t , a[5001], sis[5001], next[5001];
int minim, maxim , poz;

void Citire()
{
	int i;
	ifstream fin ("sis.in");
	fin>>n;
	for (i=1;i<=n;i++)
		 fin>>a[i];
	fin.close();
}

 void Sis()
 {
	int i,j,p;
	sis[n]=1;next[n]=n+1;
	for (i=n-1;i>=1;i--)
	{
		t=a[i];
		minim=1000001;
		p=n+1;
		maxim=1000001;
		for (j=i+1;j<=n;j++)
		  if ((t<=a[j])&&(a[j]<=minim)&&(maxim>sis[j]))
		  {
			  minim=a[j];
			  maxim=sis[j];
			  p=j;
		  }
		if (p<=n)
		{
			sis[i]=1+maxim;
			next[i]=p;
		}
		else 
		{
			next[i]=n+1;
			sis[i]=1;
		}
	}
	
	 minim=a[1]; poz = 1 ;
	 maxim=sis[1]; 
	 for (i=2;i<=n;i++)
	    if (minim>a[i]) 
		{
			minim=a[i];
			if (maxim<=sis[i]) { maxim=sis[i]; poz = i ; }
		}
	
 }
 
 void PrintSol()
 {
	//int i;
	ofstream fout("sis.out");
	fout<<maxim<<"\n";
	while (poz<=n)
	{
		fout<<poz<<" " ;
		poz = next[poz] ;
	}
	
	fout.close();
 }

 int main ()
 {
   Citire();
   Sis();
   PrintSol();
   return 0;
 }