Cod sursa(job #561936)

Utilizator blastoiseZ.Z.Daniel blastoise Data 21 martie 2011 23:19:13
Problema Subsir 2 Scor 68
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>
#include <string.h>

#define Dim 5001
#define INF ((1<<31)-1)

int v[Dim],use[Dim];

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

int main()
{
	int N,i,j,min,max,pos,ok,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=INF;
		d[i].pos=N+1;
		min=INF;
		for(j=i+1;j<=N;j++)
		{
			if(v[i]<=v[j]&&min>v[j])
				if(d[i].x>d[j].x+1)
				{
					d[i].x=d[j].x+1;
					d[i].pos=j;
				}
			if(v[i]<=v[j]) use[j]=1;
			if(min>v[j]&&v[j]>=v[i]) min=v[j];
		}
		if(d[i].x==INF) d[i].x=1;
	}

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

	freopen("subsir2.out","w",stdout);
	
	printf("%d\n",max);

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

	return 0;
}