Cod sursa(job #319292)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 31 mai 2009 11:34:05
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#define inf 0x3f3f
int n,poz,min,rez=inf;
int v[5005];
int pred[5005];
int ok[5005];
int sol[5005];

void read()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	min=inf;
	int i;
	for(i=0;i<n;i++)
	{
		scanf("%d",&v[i]);
		if(min<=v[i])
			continue;
		ok[i]=1;
		min=v[i];
	}
}

void rezx()
{
	int i,j,min;
	for(i=n-1;i>=0;i--)
	{
		sol[i]=min=inf;
		pred[i]=-1;
		for(j=i+1;j<n;j++)
		{
			if(v[j]<v[i])
				continue;
			if(min>v[j] && (sol[i]>sol[j]+1 || (sol[i]==sol[j]+1 && v[j]<v[pred[i]])))
			{
				sol[i]=sol[j]+1;
				pred[i]=j;
			}
			if(min>v[j])
				min=v[j];
		}
		if(sol[i]==inf)
		{
			sol[i]=1;
			pred[i]=i;
		}
		if(ok[i] && (rez>sol[i] || (rez==sol[i] && v[i]<v[poz])))
		{
			rez=sol[i];
			poz=i;
		}
	}
	printf("%d\n",rez);
	for(i=poz;i!=pred[i];i=pred[i])
		printf("%d ",i+1);
	printf("%d\n",i+1);
}

int main()
{
	read();
	rezx();
	return 0;
}