Cod sursa(job #16192)

Utilizator raula_sanChis Raoul raula_san Data 12 februarie 2007 16:19:16
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>

#define dim 5005
#define inf 0x3f3f3f

int N, P, A[dim], L[dim], T[dim], ok[dim];

void Read_data();
void Solve();
void Write();

int main()
{
	Read_data();
	Solve();
	Write();
	
	return 0;
}

void Read_data()
{
	freopen("subsir2.in", "r", stdin);
	scanf("%d", &N);
	
	int i, min=inf;
	for(i=1; i<=N; ++i)
	{
		scanf("%d", A+i);
		if( A[i] < min )
		{
			min = A[i];
			ok[i] = 1;
		}
	}
	
	fclose(stdin);
}

void Solve()
{
	int i, j, min, best=inf, Vmin=inf;
	
	for(i=N; i>=1; --i)
	{
		L[i] = min = inf;
		for(j=i+1; j<=N; ++j)
			if( A[j] >= A[i] && A[j] < min )
			{
				min = A[j];
				
				if( L[j]+1 < L[i] )
				{
					L[i] = L[j]+1;
					T[i] = j;
				}
				else if( L[j]+1 == L[i] && A[j] < A[T[i]] )
					T[i] = j;
			}

		if( !T[i] ) L[i] = 1;

		if( ok[i])
			if( L[i] < best || L[i] == best && A[i] < Vmin )
			{
				best = L[i];
				Vmin = A[i];
				P = i;
			}
	}
}

void Write()
{
	freopen("subsir2.out", "w", stdout);
	printf("%d\n", L[P]);
	
	while( P )
	{
		printf("%d ", P);
		P = T[P];
	}
	
	fclose(stdout);
}