Cod sursa(job #204528)

Utilizator vlad.maneaVlad Manea vlad.manea Data 24 august 2008 21:57:09
Problema Subsir 2 Scor 94
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <stdio.h>
#define nmax 5050
#define infinit 1010101

int N, i, uly, val, j, lgm;

int ult[nmax], ans[nmax], A[nmax], max[nmax], scm[nmax];

void recursie(int i)
{
	if (ult[i])
		recursie(ult[i]);

	ans[++ans[0]] = i;
}

int main()
{
	freopen("subsir2.in", "r", stdin);
	freopen("subsir2.out", "w", stdout);

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

	for (lgm = infinit, i = 1; i <= N; ++i)
		lgm = A[i] < lgm? A[i]: lgm;

//	for (i = 1; i <= N; A[i++] -= lgm - 1);

	for (max[1] = A[1], i = 2; i <= N; ++i)
		max[i] = max[i-1] > A[i]? max[i-1]: A[i];

	for (i = 1; i <= N; ++i)
	{
		for (val = -infinit, scm[i] = infinit, j = i-1; j >= 1; j--)
		{
			if (A[j] <= A[i] && scm[j] + 1 < scm[i] && A[j] > val)
			{
				scm[i] = scm[j] + 1;
				ult[i] = j;
			}
			if (A[j] <= A[i])
				val = A[j] > val? A[j]: val;
		}

		scm[i] = scm[i] == infinit? 1: scm[i];
	}

	for (max[N] = A[N], i = N-1; i >= 1; i--)
		max[i] = max[i+1] > A[i]? max[i+1]: A[i];

	for (i = 1, val = lgm = infinit; i <= N; ++i)
		if (A[i] > max[i+1] && (scm[i] < lgm || scm[i] == lgm && A[i] < val))
		{
			val = A[i];
			lgm = scm[i];
			uly = i;
		}

	recursie(uly);

	printf("%d\n", ans[0]);

	for (i = 1; i < ans[0]; ++i)
		printf("%d ", ans[i]);

	printf("%d\n", ans[i]);

	return 0;
}