Cod sursa(job #501413)

Utilizator loginLogin Iustin Anca login Data 14 noiembrie 2010 21:50:43
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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[n]=1;
	for(int i=n-1;i;--i)
	{
		val=2000000;
		for(int j=i+1;j<=n;++j)
			if (v[i]<=v[j])
			{
				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, lmin=DIM, uv;
	for(int i=1;i<=n;++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;
		}
	freopen("subsir2.out", "w", stdout);
	printf("%d\n", l[up]);
	for(int i=up;i;i=p[i])
		printf("%d ", i);
}

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