Cod sursa(job #342953)

Utilizator raduzerRadu Zernoveanu raduzer Data 24 august 2009 14:50:27
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX_N = 5010;

int n;
int a[MAX_N], d[MAX_N], t[MAX_N];

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

	scanf("%d", &n);

	for (i = 1; i <= n; ++i)
		scanf("%d", a + i);

	d[n] = 1;
	t[n] = n;

	for (i = n - 1; i; --i)
	{
		int k = INF;
		d[i] = INF;

		for (j = i + 1; j <= n; ++j)
		{
			if (j > i + 1 && k >= a[j - 1] && a[j - 1] >= a[i])
				k = a[j - 1];

			if (a[i] <= a[j] && d[j] + 1 <= d[i] && k > a[j])
					d[i] = d[j] + 1, t[i] = j;
		}

		if (d[i] == INF)
			d[i] = 1, t[i] = i;
	}

	int sol = INF, p = 0, mn = INF;
	a[0] = INF;

	for (i = 1; i <= n; ++i)
	{
		if ((d[i] < sol || (d[i] == sol && a[i] < a[p])) && a[i] < mn)
			sol = d[i], p = i;

		if (a[i] < mn)
			mn = a[i];
	}

	printf("%d\n", sol);

	for (; t[p] != p; p = t[p])
		printf("%d ", p);
	printf("%d\n", p);
}