Cod sursa(job #410464)

Utilizator prisonbreakMichael Scofield prisonbreak Data 4 martie 2010 13:37:30
Problema Subsir 2 Scor 38
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#define MINV 100000
#define nmax 5005
using namespace std;

int N, i, j, best [nmax], a [nmax], poz [nmax], afis [nmax], cnt;
int MIN, maxim , t, maxv;
int main () {

	freopen ("subsir2.in", "r", stdin);
	freopen ("subsir2.out", "w", stdout);
	scanf ("%d\n", &N);
	for (i = 1; i <= N; i++)
		scanf ("%d", &a [i]);
	best [1] = 1;
	poz [1] = 1;
	for (i = 2; i <= N; i++) {
		MIN = MINV;
		maxv = 0;
		for (j = 1; j < i; j++) 
			if (a [i] >= a [j])
				if (maxv < a [j]) {
					maxv = a [j];
					MIN = best [j] + 1, poz [i] = j;
				}
			if (MIN == MINV)  best [i] = 1, poz [i] = i;
			else	best [i] = MIN;
	}
	/*for (i = 1; i <= N; i++)
		printf ("%d ", a [i]);
	printf ("\n");
	for (i = 1; i <= N; i++)
		printf ("%d ", best [i]);
	printf ("\n");
	*/for (i = 1; i <= N; i++)
		if (maxim < best [i])
			maxim = best [i],maxv = a [i], t = i;
		else if (maxim == best [i])
			if (maxv > a [i]) 
				t = i,maxv = a [i];
	printf ("%d\n", maxim);
	while (t) {
		afis [++cnt] = t;
		if (t == poz [t]) break;
		t = poz [t];
	}
	for ( ; cnt > 0; --cnt) printf ("%d ", afis [cnt]);
	return 0;
}