Cod sursa(job #15222)

Utilizator raula_sanChis Raoul raula_san Data 11 februarie 2007 11:33:37
Problema Subsir 2 Scor 22
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<cstdio>
#define dim 5005

int N, M, p, A[dim], T[dim];
long Min = 1000005, X[dim];

void read();
void dynamics();
void write();

int main()
{
	read();
	dynamics();
	write();
	
	return 0;
}

void read()
{
	freopen("subsir2.in", "r", stdin);
	scanf("%d", &N);
	
	int i;
	for(i=1; i<=N; ++i)
	{
		scanf("%ld", X+i);
		if(X[i] < Min)
		{
			Min = X[i];
			p = i;
		}
	}
	fclose(stdin);
}

void dynamics()
{
	int i, j;
	A[N] = 1; T[N] = 0;
	
	for(i=N-1; i; --i)
	{
		Min = 1000005;
		for(j=i+1; j<=N; ++j)
			if(X[j] >= X[i] && X[j] < Min)
			{
				Min = X[j];
				A[i] = A[j]+1;
				T[i] = j+1;
			}
			else if(X[j] >= X[i] && X[j] == Min && A[j]+1 < A[i])
			{
				A[i] = A[j]+1;
				T[i] = j+1;
			}
		if(!A[i])
		{
			A[i] = 1;
			T[i] = 0;
		}
	}
}

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