Cod sursa(job #415977)

Utilizator indestructiblecont de teste indestructible Data 12 martie 2010 00:30:50
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#define NMAX 5005
#define INF 2000000000
int n,A[NMAX],B[NMAX],rez=INF,next[NMAX],poz,val=INF;
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&A[i]);
}
inline int min(int a,int b)
{
	return a<b ? a : b;
}
void solve()
{
	int i,j,m;
	for (i=n; i>=1; i--)
	{
		m=INF;
		B[i]=INF;
		for (j=i+1; j<=n; j++)
			if (A[j]>=A[i] && A[j]<m)
			{
				m=A[j];
				if (B[i]>=B[j])
				{
					B[i]=B[j];
					next[i]=j;
				}
			}
		if (B[i]==INF)
			B[i]=1;
		else
			B[i]++;
	}
}
void show()
{
	int i,m=INF;
	for (i=1; i<=n; i++)
		if (A[i]<m)
		{
			m=min(m,A[i]);
			if (rez==B[i])
				if (A[i]<val)
					val=A[i],poz=i;
			if (rez>B[i])
			{
				rez=B[i];
				val=A[i];
				poz=i;
			}
		}
	printf("%d\n",rez);
}
void reconst(int poz)
{
	if (poz==0)
		return ;
	printf("%d ",poz);
	reconst(next[poz]);
}
int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	read();
	solve();
	show();
	reconst(poz);
	printf("\n");
	return 0;
}