Cod sursa(job #495472)

Utilizator gabipurcaruGabi Purcaru gabipurcaru Data 25 octombrie 2010 14:08:44
Problema Subsir 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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],minim;
bool ok[MAXN];

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