Cod sursa(job #203141)

Utilizator damaDamaschin Mihai dama Data 14 august 2008 08:44:33
Problema Subsir 2 Scor 59
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <string.h>

const int inf = 1000001;

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

	int n, l[5001], r[5001], next[5001], v[5001];
	int i, j, min, max;


	scanf("%d", &n);

	for(i = 1; i <= n; ++i)
	{
		l[i] = r[i] = inf;
	}
	v[0] = inf;
	memset(next, 0, sizeof(next));

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

	for(i = 1; i <= n; ++i)
	{
		max = -inf;
		for(j = i - 1; j > 0; --j)
		{
			if(v[j] < v[i])
			{
				if(v[j] > max)
				{
					max = v[j];
					if(l[j] + 1 < l[i])
					{
						l[i] = l[j] + 1;
					}
				}
			}
		}
		if(l[i] == inf)
		{
			l[i] = 0;
		}
	}

	for(i = n; i > 0; --i)
	{
		min = inf;
		for(j = i + 1; j <= n; ++j)
		{
			if(v[j] > v[i])
			{
				if(v[j] < min)
				{
					min = v[j];
					if(r[j] + 1 < r[i] || (r[j] + 1 == r[i] && v[next[i]] > v[j]))
					{
						r[i] = r[j] + 1;
						next[i] = j;
					}
				}
			}
		}
		if(r[i] == inf)
		{
			r[i] = 0;
		}
	}

	int sol = inf, pos;

	for(i = 1; i <= n; ++i)
	{
		if(l[i] == 0)
		{
			if(l[i] + r[i] < sol || (l[i] + r[i] == sol && v[i] < v[pos]))
			{
				sol = l[i] + r[i];
				pos = i;
			}
		}
	}
	printf("%d\n", sol + 1);

	while(pos)
	{
		printf("%d ", pos);
		pos = next[pos];
	}
	printf("\n");



	return 0;
}