Cod sursa(job #498459)

Utilizator darrenRares Buhai darren Data 5 noiembrie 2010 10:44:44
Problema Subsir 2 Scor 46
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 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] && minS[j] + 1 <= minS[i])
			{
				minS[i] = minS[j] + 1;
				T[i] = j;
			}
			//else if (maxn < V[j] && minS[j] + 1 == minS[i])
			//	if ()
			
			if (V[j] <= V[i] && V[j] >=	maxn)
				maxn = V[j];
		}
	}
	
	for (int i = 1; i <= N; ++i)
		if(next[i] && minS[i] < result)
		{
			result = minS[i];
			pos = i;
		}
	
	fout << result << '\n';
	reconst(pos);
	
	fin.close();
	fout.close();
}

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