Cod sursa(job #340394)

Utilizator raduzerRadu Zernoveanu raduzer Data 14 august 2009 15:26:33
Problema Subsir 2 Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 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]);

	memset(d, INF, sizeof(d));

	for (i = n; i; --i)
	{
		int mn = INF;

		for (j = i + 1; j <= n; ++j)
		{
			if (a[i] < a[j] && a[j] < mn && d[i] == d[j] + 1 && a[j] < a[t[i]])
				t[i] = j;

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

			mn = min(mn, a[j]);
		}

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

	int mx = 0, p = 0;

	for (i = 1; i <= n; ++i)
		if (d[i] > mx)
			mx = d[i], p = i;

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

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