Cod sursa(job #340474)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 14 august 2009 19:20:15
Problema Subsir 2 Scor 52
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>
#define N 5005
#define NR 1000005
int n,v[N],a[N],t[N],min,rez,poz_f;
int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	int i,j,max,poz,poz2;
	for (i=1; i<=n; i++)
		scanf("%d",&v[i]);
	for (i=n; i>=1; i--)
	{
		max=N;
		poz=0;
		poz2=0;
		min=NR;
		for (j=i+1; j<=n; j++)
			if (v[j]>v[i])
			{
				if (a[j]==max)
					if (v[j]<v[poz])
					{
						poz=j;
						t[i]=j;
					}
				if (a[j]<max)
				{
					max=a[j];
					a[i]=max+1;
					t[i]=j;
					poz=j;
				}
				if (v[j]<min)
				{
					min=v[j];
					poz2=j;
				}
			}
		if (max==N)
			a[i]=1;
		else
		{
			if (poz2<poz)
			{
				a[i]=a[poz2]+1;
				t[i]=poz2;
			}
		}
		if (a[i]>rez)
		{
			rez=a[i];
			poz_f=i;
		}
	}
	printf("%d\n",rez);
	while (poz_f)
	{
		printf("%d ",poz_f);
		poz_f=t[poz_f];
	}
	return 0;
}