Cod sursa(job #360352)

Utilizator andrei_vs2009Cozma Andrei andrei_vs2009 Data 31 octombrie 2009 10:38:41
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>

using namespace std;

int n, a[5001], sis[5001], next[5001];
int min, poz;

void Citire()
{
	int i;
	ifstream fin ("subsir2.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--)
	{
		min=1000001;
		p=n+1;
		val=1000001;
		for (j=i+1;j<=n;j++)
		  if ((min<sis[j])&&(a[i]<=a[j])&&(a[j]<val))
		  {
			  min=sis[j];
			  val=a[j];
			  p=j;
		  }
		if (p<=n)
		{
			sis[i]=1+min;
			next[i]=p;
		}
		else 
		{
			next[i]=n+1;
			sis[i]=1;
		}
	}
	
	 min=sis[1]; poz = 1 ;
	 for (i=2;i<=n;i++)
	    if (min>sis[i]) 
		{
			min=sis[i];
			if (min<=sis[i]) { min=sis[i]; poz = i ; }
		}
	
 }
 
 void PrintSol()
 {
	ofstream fout("subsir2.out");
	fout<<maxim<<"\n";
	while (poz<=n)
	{
		fout<<poz<<" " ;
		poz = next[poz] ;
	}
	
	fout.close();
 }

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