Cod sursa(job #1235376)

Utilizator IulianBoboUAIC Boboc Iulian IulianBobo Data 29 septembrie 2014 18:08:53
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
using namespace std;

int n,a[5001], best[5001], maxLength, sol[5001];

ifstream f("subsir2.in");
ofstream g("subsir2.out");

void readData()
{
	f >> n;
	for (int i = 1; i <= n; ++i) f >> a[i];
	f.close();
}

void compute()
{
	int max = 0, pos = 1, ok = 1;
	best[1] = 1;
	for (int i = 2; i <= n; ++i)
	{
		max = 0;
		for (int j = 1; j < i; ++j)
		{
			if (a[j] <= a[i] && best[j]>max) max = best[j];
		}
		best[i] = max + 1;
	}
	for (int i = 2; i <= n; ++i) if (best[i] == 1) pos = i;
	maxLength = 1;
	sol[maxLength] = pos;
	for (int i = pos; i <= n;)
	{
		max = 1000001;
		ok = 0;
		for (int j = i + 1; j <= n; ++j)
		{
			if (a[j] < max && best[j] == maxLength+1)
			{
				max = a[j];
				pos = j;
				ok = 1;
			}
		}
		if (ok)
		{
			sol[++maxLength] = pos;
			i = pos;
		}
		else break;
	}
	g << maxLength << "\n";
	for (int i = 1; i <= maxLength; ++i) g << sol[i] << " ";
	g.close();
}

int main()
{
	readData();
	compute();
	return 0;
}