Cod sursa(job #315314)

Utilizator Mishu91Andrei Misarca Mishu91 Data 14 mai 2009 23:01:32
Problema Subsir 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <cstdio>
#include <cstring>

#define MAX_N 5005
#define INF 0x3f3f3f

int N, Nr = INF;
int V[MAX_N], S[MAX_N], Ant[MAX_N], Sol[MAX_N];
char Tr[MAX_N];

void citire()
{
	scanf("%d",&N);
	
	for(int i = 1; i <= N; ++i)
		scanf("%d",V+i);
}

inline int Min(const int &A, const int &B)
{
	return ((A) < (B))? (A) : (B);
}

inline bool cmp(int A[MAX_N], int B[MAX_N], int Nr)
{
	for(int i = 1; i <= Nr; ++i)
	{
		if(A[i] < B[i]) return 1;
		if(A[i] > B[i]) return 0;
	}
	return 0;
}

void solve()
{
	for(int i = N; i; --i)
	{
		Ant[i] = 0;
		S[i] = 1;
		
		int max = INF, min = INF;
		for(int j = i+1; j <= N; ++j)
			if(V[i] <= V[j])
			{
				if(max == S[j] && V[j] < min)
	  				Ant[i] = j;
				
				if(max > S[j] && V[j] < min)
				{
					max = S[j];
	  				Ant[i] = j;
				}
				
				min = Min(min, V[j]);
			}
		if(max) S[i] = S[Ant[i]] + 1;
	}
	
	for(int i = 1; i <= N; ++i)
	{
		char ok = 0;
		
		for(int j = 1; j < i; ++j)
			if(V[j] <= V[i])
				ok = 1;
		
		Tr[i] = ok;
	}
	
#ifdef _HOME_
	for(int i = 1; i <= N; ++i)
		fprintf(stderr,"%d %d %d %c\n",V[i], S[i], Ant[i], Tr[i]);
#endif
	
	for(int i = 1; i <= N; ++i)
	{
		if(S[i] < Nr && Tr[i] == 0)
		{
			Nr = S[i];
			int k = i, p = 0;
			while(k)
			{
				Sol[++p] = k;
				k = Ant[k];
			}
#ifdef _HOME_
		for(int i = 1; i <= Nr; ++i)
			fprintf(stderr,"%d ",Sol[i]);
		fprintf(stderr,"\n");
#endif
		}
		
		if(S[i] == Nr && Tr[i] == 0)
		{
			int Aux[MAX_N];
			
			int k = i, p = 0, ok = 2;
			while(k)
			{
				Aux[++p] = k;
				k = Ant[k];
				
				if(ok == 2)
					if(V[Aux[p]] < V[Sol[p]])
						ok = 1;
					else
						ok = 0;
			}
			
			if(ok)
			{
				memcpy(Sol, Aux, sizeof Aux);
#ifdef _HOME_
				for(int i = 1; i <= Nr; ++i)
					fprintf(stderr,"%d ",Sol[i]);
				fprintf(stderr,"\n");
#endif
			}
		}
	}
	
	printf("%d\n",Nr);
	
	for(int i = 1; i <= Nr; ++i)
		printf("%d ",Sol[i]);
			
}

int main()
{
	freopen("subsir2.in","rt",stdin);
	freopen("subsir2.out","wt",stdout);
	
	citire();
	solve();
}