Cod sursa(job #696840)

Utilizator andrici_cezarAndrici Cezar andrici_cezar Data 28 februarie 2012 20:23:07
Problema Subsir 2 Scor 42
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <cstdio>

long N, i, j, lgmax, pos, max, aux, nr, posm, a[5001], b[5001], c[5001], d[5001], viz[5001];

int main() {
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w", stdout);
	
		scanf("%ld", &N);
		
		for (i = 1; i <= N; ++i)
			scanf("%ld", &a[i]);
		c[N] = N;
		max = 1000001;
		for (i = N; i > 0; --i) {
			lgmax = 0;
			pos = i;
			for (j = i+1; j <= N; ++j) {
				if (a[j] > a[i] && b[j]+1 > lgmax) {
					lgmax = b[j]+1;
					pos = j;
				}
				if (a[j] > a[i]) {
					viz[j] = 1;
				}
			}
			
			b[i] = lgmax;
			c[i] = pos;
		}
		
		for (i = 1; i <= N; ++i) {
			if (viz[i] == 0) {
				nr = 0;
				posm = i;
				while (posm != c[posm]) {
					++nr;
					posm = c[posm];
				}
				posm = i;
				max = nr;
				break;
			}
		}

		printf("%ld\n", max+1);
		while (posm != c[posm]) {
			printf("%ld ", posm);
			posm = c[posm];
		}
		printf("%ld\n", posm);
		
	return 0;
}