Cod sursa(job #698044)

Utilizator lily3Moldovan Liliana lily3 Data 29 februarie 2012 12:09:51
Problema Subsir 2 Scor 83
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
using namespace std;

int i,j,n,m,a[5010],poz[5010],l[5010],min1,max1,pozitie;
int main()
{
	FILE *f=fopen("subsir2.in","r");
	FILE *g=fopen("subsir2.out","w");
	fscanf(f,"%d",&n);
	for(i=1;i<=n;++i)
		fscanf(f,"%d",&a[i]);
	for(i=n;i>=1;--i)
	{
		min1=max1=1<<30;
		for(j=i+1;j<=n;++j)
			if(a[i]<=a[j]&&min1>a[j])
			{
				min1=a[j];
				if(l[j]<=max1)
					max1=l[j],pozitie=j;
			}
			if(min1==1<<30)
				l[i]=1;
			else
				l[i]=l[pozitie]+1,poz[i]=pozitie;
	}
	min1=l[1];
	pozitie=1;
	j=a[1];
	for(i=2;i<=n;++i)
		if(a[i]<j)
		{
			if(min1>l[i])
				min1=l[i],pozitie=i;
			j=a[i];
		}
		fprintf(g,"%d\n",min1);
		while(pozitie)
		{
			fprintf(g,"%d ",pozitie);
			pozitie=poz[pozitie];
		}
		return 0;
}