Cod sursa(job #501411)

Utilizator loginLogin Iustin Anca login Data 14 noiembrie 2010 21:43:39
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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], l[i]=DIM;
}

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

void write ()
{
	int up, sol[DIM], lmin=DIM, uv;
	for(int i=n;i;--i)
		if (!cpt[i])
		{
			if (l[i]<lmin)
				lmin=l[i], up=i, uv=v[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;
}