Cod sursa(job #561755)

Utilizator blastoiseZ.Z.Daniel blastoise Data 21 martie 2011 15:38:48
Problema Subsir 2 Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <string.h>

#define Dim 5001
#define INF 2147483647

int v[Dim];

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

int main()
{
	int N,i,j,size,pos,min,ok;

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

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

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

	size=1;
	d[N].x=1;
	d[N].pos=-1;
	d[N].i=-INF;
	for(i=N-1;i>0;i--)
	{
		d[i].x=N+1;
		d[i].pos=-1;
		d[i].i=-INF;

		for(j=i+1;j<=N;j++)
			if(v[i]<=v[j])
			{
				if(d[i].x>d[j].x+1&&v[j]>=d[i].i) d[i].x=d[j].x+1;
				d[j].pos=1;
				d[i].i=v[j];
				ok=1;
			}
		if(d[i].x==N+1) d[i].x=1;
	}

	size=N+1;
	for(i=1;i<=N;i++)
		if(d[i].pos==-1)
			if(size>d[i].x) size=d[i].x;

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

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

	pos=0;
	ok=0;
	while(size)
	{
		min=INF;
		for(i=pos+1;i<=N;i++)
			if(ok)
			{
				if(d[i].x==size)
					if(min>v[i])
					{
						min=v[i];
						pos=i;
					}
			}
			else
			if(d[i].x==size&&d[i].pos==-1)
				if(min>v[i])
				{
					min=v[i];
					pos=i;
				}
		ok=1;
		printf("%d ",pos);
		size--;
	}

	printf("\n");

	return 0;
}