Mai intai trebuie sa te autentifici.

Cod sursa(job #499454)

Utilizator darrenRares Buhai darren Data 9 noiembrie 2010 20:06:43
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 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 = V[i];
		}

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

	minS[1] = 1;
	V[0] = -INF + 1;

	for (int i = 2; i <= N; ++i)
	{
		int maxn = -INF;

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

			if (V[j] <= V[i] && V[j] > maxn)
				maxn = V[j];
		}
	}

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

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

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

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