Cod sursa(job #501367)

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

void read ()
{
	ifstream fin ("subsir2.in");
	fin>>n;
	for(int i=1;i<=n;++i)
		fin>>v[i], l[i]=DIM, poz[i]=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] && (v[poz[j]]>v[i] || poz[j]==j))
			{
				if (l[j]+1<l[i])
				{
					l[i]=l[j]+1, p[i]=j, cpt[j]=1;
					if (poz[j]==j)
						poz[j]=i;
					else if (v[poz[j]]>v[i])
						poz[j]=i;
				}
				else
					if (l[j]+1==l[i] && v[j]<v[p[i]])
					{
						p[i]=j, cpt[j]=1;
						if (poz[j]==j)
							poz[j]=i;
						else if (v[poz[j]]>v[i])
							poz[j]=i;
					}
					
			}
		if (l[i]==DIM)
			l[i]=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;
}