Cod sursa(job #562382)

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

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

int v[Dim],d[Dim],use[Dim];

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

	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));
	min=INF;
	d[N]=1;

	for(i=N-1;i>0;i--)
	{
		d[i]=N+1;
		min=INF;
		for(j=i+1;j<=N;j++)
		{
			if(v[i]<=v[j]&&min>v[j])
				if(d[i]>d[j]+1) d[i]=d[j]+1;
			if(v[i]<=v[j])
			{
				use[j]=1;
				if(min>v[j]) min=v[j];
			}
		}
		if(d[i]==N+1) d[i]=1;
	}

	max=-INF;
	for(i=1;i<=N;i++)
		if(!use[i])
			if(max>d[i]) max=d[i];

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

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

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

	while(1)
	{
		printf("%d ",pos);
		max--;
		min=INF;
		p=INF;
		for(i=pos+1;i<=N;i++)
		{
			if(d[i]==max)
				if(v[pos]<=v[i]&&(v[i]<v[p]||p==INF)&&v[i]<min)
					p=i;
			if(v[pos]<=v[i]&&v[i]<min) min=v[i];
		}
		if(p==INF) break;
		pos=p;
	}

	return 0;
}