Cod sursa(job #458343)

Utilizator aladinaladin aladinn aladin Data 24 mai 2010 17:08:15
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <cstdio>
int n,i,v[5004],x[5004],l[5004],j,sol;

int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i) scanf ("%d",&v[i]);
	
	x[n]=1;sol=n;
	for (i=n-1;i>0;--i)
	{
		int max=0,min=0;
		for (j=i+1;j<=n;++j)
			if (v[j]>v[i])
			{
				if (x[j]>max)
				max=x[j],min=j; else
					if ((x[j]==max) && (v[min]>v[j]))
						min=j;
			}
		x[i]=max+1;l[i]=min;
		if (x[i]>x[sol])
			sol=i; else
				if ((x[i]==x[sol]) && (v[i]<v[sol]))
					sol=i;
	}
	printf("%d\n",x[sol]);
	do
	{
		printf("%d ",sol);
		sol=l[sol];
	}
	while (sol>0);
	return 0;}