Cod sursa(job #716144)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 18 martie 2012 13:11:48
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
int n, a[5005],b[5005],c[5005],i,j,amin,bmin,lmin,vmin,poz,p,x;
int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for (i=n;i>=1;i--)
	{
		amin=1000001;
		bmin=n+1;
		for (j=i+1;j<=n;j++)
		{
			if (a[i]<=a[j])
			{
				c[j]=1;
				if (amin>a[j])
				{
					amin=a[j];
					if (b[j]<bmin)
					{
						bmin=b[j];
						p=j;
					}
					
				}
			}
		}
		if (bmin==n+1) b[i]=1;
		else b[i]=bmin+1;
	}
	lmin=n+1;
	amin=1000001;
	for (i=1;i<=n;i++)
	{
		if ((c[i]==0 && b[i]<lmin)||
			(c[i]==0 && b[i]==lmin && a[i]<amin))
		{
			lmin=b[i];
			amin=a[i];
			poz=i;
		}
	}
	printf("%d\n",lmin);
	printf("%d ",poz);
	for (i=2;i<=lmin;i++)
	{
		amin=1000001;
		for (j=poz+1;j<=n;j++)
		{
			if (a[poz]<=a[j])
			{
				if (amin>a[j])
				{
					amin=a[j];
					if (b[j]==lmin+1-i)
					{
						p=j;
					}
				}
			}
		}
		printf("%d ",p);
		poz=p;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}