Cod sursa(job #17433)

Utilizator webspiderDumitru Bogdan webspider Data 15 februarie 2007 21:18:36
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int rel[5001];

int ch[5001];
int maxc;
int sir[5001];
int lmin;
int asd;

int n;

bool cmpf( const int &a, const int &b )
{
	if ( sir[a] < sir[b] ) return 1;
	return 0;
}

int main()
{
	int i,j;
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);

	scanf("%d\n", &n);

	for ( i = 1; i <= n; i++ )
		scanf("%d ", &sir[i] );

	for ( i = n; i >= 1; i-- )
	{
		maxc = 10000000;
		ch[i]=1;
		
		for ( j = i+1; j <= n; j++ )
		{
			if ( sir[j] < maxc )
			{
				if ( sir[j] > sir[i] )
				{
					if ( ch[j]+1 < ch[i] || ch[i] == 1)
					{
						ch[i]= ch[j]+1;
						rel[i]=j;
					}
					else  if ( ch[j] + 1 == ch[i] )
						if ( sir[rel[i]] > sir[j] ) rel[i] = j;
					maxc = sir[j];
				}
			}
		}
	}
	maxc = sir[1];
	lmin = 1000000;
	for ( i = 1; i <= n; i++ )
	{
		if ( maxc >= sir[i] )  
		{
			if ( ch[i]<lmin ) lmin = ch[i];
			maxc = sir[i];
		}
	}
	asd = sir[1];
	sir[0] = 999990000;
	maxc = 0;
	for ( i = 1; i <= n; i ++ )
	if ( asd >= sir[i] )
	{
		if ( ch[i] == lmin ) if ( sir[maxc] > sir[i] ) maxc = i;
		asd = sir[i];
	}
	
	printf("%d\n", lmin);
	printf("%d", maxc);
	while ( rel[maxc]!=0 )
	{
		printf(" %d", rel[maxc] );
		maxc = rel[maxc];
	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}