Cod sursa(job #95304)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 28 octombrie 2007 08:45:13
Problema Subsir 2 Scor 97
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>

const int N_MAX = 5010;
const int INF = 2000000000;

int v[N_MAX], din[N_MAX], succ[N_MAX];

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

	int N, i;

	scanf("%d\n", &N);
	for (i = 1; i <= N; i ++) {
		scanf("%d ", &v[i]);
	}

	int MIN, j;

	for (i = N; i >= 1; i --) {
		
		din[i] = INF, succ[i] = i;
		MIN = INF;

		for (j = i + 1; j <= N; j ++) {
			if (v[j] < MIN && v[j] >= v[i]) {

				MIN = v[j];

				if ((din[j] + 1 < din[i]) || (din[j] + 1 == din[i] && v[j] < v[succ[i]])) {
					din[i] = din[j] + 1;
					succ[i] = j;
				} 
			}
		}

		if (din[i] == INF) din[i] = 1;
	}

	int inc = 0, l = INF;
	MIN = INF;

	for (i = 1; i <= N; i ++) {
		if (v[i] < MIN && din[i] <= l) {
			MIN = v[i];
			inc = i;
			l = din[i];
		}
	}
	printf("%d\n", l);

	i = inc;

	while (succ[i] != i) {
		printf("%d ", i);
		i = succ[i];
	}
	printf("%d\n", i);

	return 0;
}