Cod sursa(job #339284)

Utilizator savimSerban Andrei Stan savim Data 9 august 2009 11:25:56
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 5010
#define inf 2147000000

int n, sol;
int A[MAX_N], c[MAX_N], vine[MAX_N], val[MAX_N];
int sir[MAX_N];

void cit() {
	freopen("subsir2.in", "r", stdin);
	freopen("subsir2.out", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &A[i]);
}

void reconst();

void solve() {
	//c[i] = lungimea celui mai scurt subsir crescator maximal cu capul dr in i
	val[n + 1] = -inf;
	for (int i = n; i >= 1; i--) {
		c[i] = inf;
		val[i] = max(val[i + 1], A[i]);
	}

	A[0] = -inf;
	for (int i = 0; i < n; i++) {
		int p = inf;
		for (int j = i + 1; j <= n; j++) 
			if (A[j] >= A[i] && A[j] < p) {
				if (c[j] > c[i] + 1) {
					c[j] = c[i] + 1;
					vine[j] = i;
				} 
				else 
					if ((c[j] == c[i] + 1) && (A[i] < A[vine[j]]))
						vine[j] = i;

				p = A[j];
			}
	}
 
	reconst();
}

void reconst() {
	sol = inf;
	for (int i = 1; i <= n; i++) {
		if (c[i] < sol && val[i + 1] < A[i])
			sol = c[i]; 
	}

	int k = inf, poz = 1;
	for (int i = 1; i <= n; i++)
		if (c[i] == sol && val[i + 1] < A[i] && A[i] < k) {
			k = A[i];
			poz = i;
		}

	int nr = sol;
	while (poz) {
		sir[nr--] = poz;
		poz = vine[poz];
	}
}

void write() {
	printf("%d\n", sol);
	for (int i = 1; i <= sol; i++)
		printf("%d ", sir[i]);
	printf("\n");		
}

int main() {

	cit();
	solve();
	write();

	return 0;
}