Cod sursa(job #495456)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 25 octombrie 2010 13:22:07
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
// infoarena: problema/subsir2 //
#include <fstream>
#define MAXN 5010
using namespace std;

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

int x[MAXN],i,j,s[MAXN],k[MAXN],m,n,l,p,q,r[MAXN];

int main()
{
	in>>n;
	for(i=1; i<=n; i++)
		in>>x[i];
	
	s[1] = 1;
	for(i=2; i<=n; i++)
	{
		m = 0;
		for(j=1; j<n; j++)
			if(x[j] < x[i] && s[j] > s[m])
				m = j;
			
		s[i] = s[m] + 1;
		k[i] = m;
		if(s[m] == 0)
			k[i] = i;
		if(s[q] < s[i])// || s[q] == s[i] && x[q] < x[i])
			q = i;
	}
	
	out<<s[q]<<'\n';
	p = q;
	
	while(p)
	{
		r[++r[0]] = p;
		p = k[p];
	}
	
	for(i=r[0]; i>=1; --i)
		out<<r[i]<<' ';
	
	return 0;
}