Cod sursa(job #411091)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 4 martie 2010 18:37:32
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#define inf 100000
#define nmax 5005
using namespace std;

int N, i, j, best [nmax],min, a [nmax], poz [nmax], ok [nmax], cnt;
int MIN, maxim , t, maxval;
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 [N] = ok [N] = 1;
	poz [N] = N;
	for (i = N - 1; i >= 1; i--) {
		best [i] = min = inf;
		ok [i] = 1; // este un scmin incepand cu i
		for (j = i + 1; j <= N; j++)
			if (a [i] <= a [j] && a [j] < min) {				
				ok [j] = 0; //nu mai poate fi un scmin incepand cu j
				min = a [j];
				if (best [i] > best [j] + 1)
					best [i] = best [j] + 1, poz [i] = j;
				else if (best [i] == best [j] + 1)
					if (a [poz [i]] > min)
						poz [i] = j;
			}
		if (best [i] == inf) best [i] = 1, poz [i] = i;
	}
	maxim = inf;
	for (i = 1; i <= N; i++)
		if (ok [i]) 
			if (best [i] < maxim)
				maxim = best [i], t = i, maxval = a [i];
			else if (maxim == best [i] && maxval > a [i])
				t = i;
	printf ("%d\n", maxim);
	while (t) {
		printf ("%d ", t);
		if (t == poz [t]) break;
		t = poz [t];
	}
	return 0;
}