Cod sursa(job #360360)

Utilizator alexsobiMardare Alexandru Gabriel alexsobi Data 31 octombrie 2009 11:06:51
Problema Subsir 2 Scor 56
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
//#include <iostream>

using namespace std;

int a[5001],sis[5001],pred[5001],n;



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

int main()
{
	int i,k,j,min,poz,min1;
	Citire();
	sis[n]=1;
	pred[n]=n+1;
	for(i=n-1;i>=1;i--)
	{
		min=1000001;
		poz=n+1;
		sis[i]=n+1;
		for(j=i+1;j<=n;j++)
			if((a[i]<=a[j])&&(a[j]<=min)&&(sis[i]>sis[j]))
			{
				pred[i]=j;
				min=a[j];
				sis[i]=1+sis[j];
			}
		if(sis[i]==n+1) {sis[i]=1;pred[i]=n+1;}
	}
	k=1;
	for(i=2;i<=n;i++)
		if(a[k]>a[i])
			k=i;
	min=sis[1];poz=1;
	min1=a[1];
	for(i=2;i<=k;i++)
		if((a[i]<min1)&&(min>=sis[i]))
			{
				poz=i;
				min1=a[i];
				min=sis[i];
			}
		
		ofstream f("subsir2.out");
	f<<sis[poz]<<"\n";
	k=poz;
	while(k<n+1)
	{
		f<<k<<" ";
		k=pred[k];
	}
	f<<"\n";
	f.close();
	/*for(i=1;i<=n;i++)
		cout<<sis[i]<<" ";
	cout<<"\n";
	for(i=1;i<=n;i++)
		cout<<pred[i]<<" ";
	*/
	return 0;
}