Cod sursa(job #953807)

Utilizator darrenRares Buhai darren Data 27 mai 2013 13:10:48
Problema Subsir 2 Scor 83
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;

int N;
int A[5002], D[5002], T[5002];
int ST[5002];
int result = INF, where;

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

	fin >> N;
	for (int i = 1; i <= N; ++i)
		fin >> A[i];

	for (int i = N; i >= 1; --i)
	{
		D[i] = INF;

		ST[0] = 0;
		for (int j = i + 1; j <= N; ++j)
			if (A[i] <= A[j])
			{
				while (ST[0] != 0 && A[ST[ST[0]]] > A[j])
					--ST[0];
				ST[++ST[0]] = j;

				if (ST[0] == 1 && (D[ST[1]] + 1 < D[i] || (D[ST[1]] + 1 == D[i] && A[ST[1]] < A[T[i]])))
				{
					D[i] = D[ST[1]] + 1;
					T[i] = ST[1];
				}
			}

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

	int minnow = -INF;
	for (int i = 1; i <= N; ++i)
	{
		if (minnow == -INF || A[minnow] > A[i])
			minnow = i;
		if (minnow == i && result > D[i])
		{
			result = D[i];
			where = i;
		}
	}

	fout << result << '\n';
	while (where != 0)
	{
		fout << where << ' ';
		where = T[where];
	}
	fout << '\n';

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