Cod sursa(job #181759)

Utilizator amadaeusLucian Boca amadaeus Data 18 aprilie 2008 21:48:36
Problema Subsir 2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>

#define NX 5010
#define INF (0x3f3f3f3f)

int N, v[ NX ], c[ NX ], t[ NX ];

void cit() {
	int i;

	scanf( "%d", &N );
	for( i = 1; i <= N; i++ )
		scanf( "%d", v+i );

}

int i, j, k, min;

void rez() {

	v[0] = -INF;
	v[N+1] = INF - 1;
	c[N+2] = INF;

	for( i = N; i>=0; i-- ) {
		min = INF;
		k = N+2;
		
		for( j = i+1; j <= N+1; j++ ) {
			if( v[j] >= v[i] && v[j] < min )
				if( c[j] < c[k] || (c[j] == c[k] && v[j] < v[k] ) )
					k = j;

			if( v[j] >= v[i] && v[j] <= min )
				min = v[j];
		}

		c[i] = 1 + c[k];
		t[i] = k;
	}
}

void scr() {
	int i;

	printf( "%d\n", c[0] - 1 );
	
	for( i = t[0]; i <= N; i = t[i] )
		printf( "%d ", i );

	printf( "\n" );
}

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

	cit();
	rez();
	scr();

	return 0;
}