Cod sursa(job #498562)

Utilizator darrenRares Buhai darren Data 5 noiembrie 2010 15:28:37
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

const int INF = 0x3f3f3f3f;

void reconst(int aux);

int N;
int V[5002], T[5002], minS[5002];
bool next[5002];
int result = INF, pos;

int main()
{
	fin >> N;
	for (int i = 1; i <= N; ++i)
		fin >> V[i];

	int auxm = -INF;
	for (int i = N; i >= 1; --i)
		if (V[i] > auxm)
		{
			next[i] = true;
			auxm = max(auxm, V[i]);
		}

	for (int i = 1; i <= N; ++i)
		minS[i] = INF;

	minS[1] = 1;
	for (int i = 2; i <= N; ++i)
	{
		int maxn = -INF;

		for (int j = i - 1; j >= 1; --j)
		{
			if (maxn < V[j] && V[j] <= V[i] && minS[j] + 1 < minS[i])
			{
				minS[i] = minS[j] + 1;
				T[i] = j;
			}
			else if (maxn < V[j] && V[j] <= V[i] && minS[j] + 1 == minS[i] && V[T[i]] > V[j])
				T[i] = j;
			if (V[j] <= V[i] && V[j] > maxn)
				maxn = V[j];
		}

		if (minS[i] == INF)
			minS[i] = 1;
	}

	for (int i = 1; i <= N; ++i)
		if(next[i] && minS[i] < result)
		{
			result = minS[i];
			pos = i;
		}
		else if (next[i] && minS[i] == result && V[i] < V[pos])
			pos = i;

	fout << result << '\n';
	reconst(pos);

	fin.close();
	fout.close();
}

void reconst(int aux)
{
	if (aux == 0)
		return;
	reconst(T[aux]);
	fout << aux << ' ';
}