Cod sursa(job #696777)

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

long N, i, j, lgmax, pos, max, posm, a[5001], b[5001], c[5001], d[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[1] = 1;
		max = 1000000;
		for (i = 2; i <= N; ++i) {
			lgmax = 1000000;
			pos = i;
			for (j = 1; j < i; ++j) {
				if (a[j] < a[i] && lgmax > b[j]+1) {
					lgmax = b[j]+1;
					pos = j;
				}
			}
			
			b[i] = lgmax;
			c[i] = pos;
			if (lgmax < max) {
				max = lgmax;
				posm = i;
			}
		}
		
		printf("%ld\n", max+1);
		while (posm != c[posm]) {
			d[++d[0]] = posm;
			posm = c[posm];
		}
		d[++d[0]] = posm;
		for (i = d[0]; i > 0; --i) {
			printf("%ld ", d[i]);
		}
		printf("\n");
	
	return 0;
}