Cod sursa(job #339264)

Utilizator savimSerban Andrei Stan savim Data 9 august 2009 10:46:12
Problema Subsir 2 Scor 67
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 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], fin[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
	for (int i = n; i >= 1; i--) {
		c[i] = inf;
		val[i] = max(val[i + 1], A[i]);
	}
	c[1] = 1;

	for (int i = 1; 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];
		fin[i] = 0;
	}
	A[0] = inf;

	for (int i = 1; i <= n; i++) 
		if (c[i] == sol && val[i + 1] < A[i]) {
			
			int k = i, nr = sol;
			while (k) {
            	sir[nr--] = k;
				k = vine[k];
			}

			int comp = 0;
			for (int j = 1; j <= sol; j++) {
				if (A[sir[j]] < A[fin[j]]) {
					comp = 1;
					break;
				}
				if (A[sir[j]] > A[fin[j]]) {
					comp = -1;
					break;
				}
			}

			if (comp)
				for (int j = 1; j <= sol; j++)
					fin[j] = sir[j];
		}
	
}

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

int main() {

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

	return 0;
}