Cod sursa(job #755879)

Utilizator Victor10Oltean Victor Victor10 Data 7 iunie 2012 22:58:46
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#define DMAX 5005

struct bestmin {
	int b, m; // b - best, m - min
};

bestmin best [DMAX];
int pre [DMAX], v [DMAX], sol [DMAX];

void makesol (int pozmaxx) {
	for (; pozmaxx; pozmaxx = pre [pozmaxx])
		sol [++ sol [0]] = pozmaxx;
}

int main () {
	
	freopen ("subsir2.in", "r", stdin);
	freopen ("subsir2.out", "w", stdout);
	
	int n, i, j, maxx, pozmaxx, minn, minn2;
	
	scanf ("%d", &n);
	
	for (i = 1; i <= n; ++ i) {
		scanf ("%d", &v [i]);
		best [i] . m = 1000005;
		minn2 = 1000005;
		
		maxx = 0;
		pozmaxx = 0;
		for (j = i - 1; j; -- j) {
			if (v [j] <= v [i])
				if ((best [j] . b > maxx) || (best [j] . b == maxx && v [j] < best [i] . m) || (best [j] . b == maxx && v [j] == best [i] . m && v [j] < minn2)) {
					maxx = best [j] . b;
					pozmaxx = j;
					minn2 = v [j];
					best [i] . m = v [j];
				}
		}
		best [i] . b = maxx + 1;
		pre [i] = pozmaxx;
	}
	
	maxx = 0; minn = 1000005; minn2 = 1000005;
	for (i = 1; i <= n; ++ i) {
		if( (best [i] . b > maxx) || (best [i] . b == maxx  && best [i] . m < minn) || (best [i] . b == maxx && best [i] . m == minn && v [i] < minn2)) {
			maxx = best [i] . b;
			minn = best [i] . m;
			pozmaxx = i;
			minn2 = v [pozmaxx];
		}
	}
	
	makesol (pozmaxx);
	printf ("%d\n", maxx);
	for (i = sol [0]; i; -- i)
		printf ("%d ", sol [i]);
}