Cod sursa(job #561735)

Utilizator blastoiseZ.Z.Daniel blastoise Data 21 martie 2011 14:35:22
Problema Subsir 2 Scor 58
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <string.h>

#define Dim 5001

int v[Dim],use[Dim];

struct vector
{
	int x,pos;
}d[Dim];

int main()
{
	int i,j,N,pos,max,aux;

	freopen("subsir2.in","r",stdin);

	scanf("%d",&N);
	for(i=1;i<=N;i++) scanf("%d",&v[i]);

	memset(d,0,sizeof(d));
	memset(use,0,sizeof(use));

	d[N].x=1;
	d[N].pos=N+1;

	for(i=N-1;i>0;i--)
	{
		d[i].x=1;
		d[i].pos=N+1;
		for(j=i+1;j<=N;j++)
			if(v[i]<v[j])
			{
				use[j]=1;
				if(d[i].x<d[j].x+1)
				{
					d[i].x=d[j].x+1;
					d[i].pos=j;
				}
				else
				if(d[i].x==d[j].x+1)
					if(v[j]<=v[d[i].pos])
						d[i].pos=j;
			}
	}

	max=N+1;
	pos=N+1;
	for(i=1;i<=N;i++)
		if(!use[i])
			if(d[i].x<max)
			{
				max=d[i].x;
				pos=i;
			}
			else
			if(d[i].x==max)
			{
				j=i;
				aux=pos;
				while(v[j]==v[aux]&&j<=N&&aux<=N)
				{
					j=d[j].pos;
					aux=d[aux].pos;
				}
				if(v[aux]>v[j]) pos=i;
			}

	freopen("subsir2.out","w",stdout);

	printf("%d\n",max);

	while(pos<=N)
	{
		printf("%d ",pos);
		pos=d[pos].pos;
	}
	printf("\n");

	return 0;
}