Cod sursa(job #501356)

Utilizator loginLogin Iustin Anca login Data 14 noiembrie 2010 20:18:34
Problema Subsir 2 Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
# include <fstream>
# define DIM 5003
using namespace std;
int n, v[DIM], p[DIM], l[DIM], cpt[DIM];

void read ()
{
	ifstream fin ("subsir2.in");
	fin>>n;
	for(int i=1;i<=n;++i)
		fin>>v[i];
}

void solve ()
{
	l[1]=1;
	for(int i=2;i<=n;++i)
		for(int j=i-1;j;--j)
			if (v[j]<=v[i])
			{
				if (l[j]+1>l[i])
					l[i]=l[j]+1, p[i]=j, cpt[j]=1;
				else
					if (l[j]+1==l[i] && v[j]<v[p[i]])
						p[i]=j, cpt[j]=1;
			}
}

void write ()
{
	int uv=2000000, up=n+1, sol[DIM], lmin=DIM;
	for(int i=n;i;--i)
		if (!cpt[i])
		{
			if (l[i]<lmin)
				lmin=l[i], uv=v[i], up=i;
			else if (l[i]==lmin && uv>v[i])
				uv=v[i], up=i;
		}
	sol[0]=0;
	do {
		sol[++sol[0]]=up;
		up=p[up];
	}
	while (up);
	freopen("subsir2.out", "w", stdout);
	printf("%d\n", sol[0]);
	for(int i=sol[0];i;--i)
		printf("%d ", sol[i]);
}

int main ()
{
	read ();
	solve ();
	write ();
	return 0;
}