Cod sursa(job #951760)

Utilizator tudorv96Tudor Varan tudorv96 Data 21 mai 2013 16:48:53
Problema Subsir 2 Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <iostream>
using namespace std;

#define in "subsir2.in"
#define out "subsir2.out"
#define N 5005
#define oo (1 << 30)

int bst[N], v[N], tata[N], n, MIN = oo, bg;
bool fiu[N];

int main () {
	ifstream fin (in);
	fin >> n;
	for (int i = 1; i <= n; ++i) {
		fin >> v[i];
		bst[i] = 1;
	}
	v[0] = oo;
	bst[0] = oo;
	for (int i = n; i; --i) {
		for (int j = i + 1; j <= n; ++j)
			if (v[i] <= v[j]) {
				fiu[j] = 1;
				if (v[tata[i]] > v[j] && bst[j] < bst[tata[i]])
					tata[i] = j;
			}
		if (tata[i])
			bst[i] = bst[tata[i]] + 1;
	}
	for (int i = 1; i <= n; ++i)
		if (!fiu[i])
			if (bst[i] < MIN || (bst[i] == MIN && v[bg] > v[i])) {
				bg = i; 
				MIN = bst[i];
			}
	ofstream fout (out);
	fout << MIN << "\n";
	while (bg) {
		fout << bg << " ";
		bg = tata[bg];
	}
	fout.close();
	return 0;
}