Cod sursa(job #696221)

Utilizator netedu_andreiFII Andrei Netedu netedu_andrei Data 28 februarie 2012 17:37:46
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<stdio.h>

long n,i,j,su,min,minp,mine,a[6000],b[6000],c[6000];

int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;i++) scanf("%ld",&a[i]);
	for(i=n;i>=1;i--)
	{
		su=1000001;
		min=1000001;
		minp=0;
		for(j=i+1;j<=n;j++)
			if(a[j]>=a[i] && min>a[j])
			{
				min=a[j];
				if (c[j]<=su) 
				{
					su=c[j];
					minp=j;
				}
			}
		b[i]=minp;
		c[i]=c[minp]+1;
	}
	min=c[1]; 
	mine=a[1];
	minp=1;
	for(i=2;i<=n;i++)
		if(a[i]<mine)
		{
			if(c[i]<=min)
			{
				minp=i;
				min=c[i];
			}
			mine=a[i];
		}
	printf("%ld\n",min);
	for(i=1;i<=min;i++)
	{
		
		printf("%ld ",minp);
		minp=b[minp];		
	}
	printf("\n");
	return 0;
}