Cod sursa(job #35364)

Utilizator alextheroTandrau Alexandru alexthero Data 21 martie 2007 23:57:02
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>

#define nmax 5005
#define inf 2000000000

int i,n,a[nmax],c[nmax],t[nmax],vmax,vmin,rez,pmin;

int main() {
	freopen("subsir2.in","r",stdin);
 	freopen("subsir2.out","w",stdout);
	
	scanf("%d",&n);
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]);

	for(int i = n; i >= 1; i--) {
		c[i] = inf;
		vmax = inf;
		for(int j = i + 1; j <= n; j++) {
			if(a[j] < vmax && a[j] >= a[i] && (c[j] + 1 < c[i] || (c[j] + 1 == c[i] && a[t[i]] > a[j]))) {
				c[i] = c[j] + 1;
				t[i] = j;
			}
			if(a[j] >= a[i] && a[j] < vmax) vmax = a[j];
		}
		if(c[i] == inf) {
			c[i] = 1;
			t[i] = -1;
		}
	}

	vmax = vmin = rez = pmin = inf;
	for(int i = 1; i <= n; i++) {
		if(a[i] < vmax && (c[i] < rez || (c[i] == rez && a[i] < vmin))) {
			rez = c[i];
			vmin = a[i];
			pmin = i;
		}
		if(a[i] < vmax) vmax = a[i];
	}

	printf("%d\n",rez);
	while(t[pmin] != -1) {
		printf("%d ",pmin);
		pmin = t[pmin];
	}
	printf("%d\n",pmin);

	return 0;
}