Cod sursa(job #540992)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 24 februarie 2011 18:43:00
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

#define maxn 5005
#define oo 200000000

int i,j,N,Min,pmin,Max,pmax;
int v[maxn],A[maxn],to[maxn];

void citire()
{
	fin >> N;
	for(i=1;i<=N;i++)
		fin >> v[i];
}

void pd()
{
	for(i=N;i;i--)
	{
		Min=oo; pmin=0; A[i]=oo;
		for(j=i+1;j<=N;j++)
		{
			if(v[j]<Min && v[j]>=v[i])
			{
				Min=v[j];
				if(A[j]+1<A[i])
				{
					A[i]=A[j]+1;
					pmin=j;
				}
				else if(A[j]+1==A[i] && v[j]<v[pmin])
					pmin=j;
			}
		}
		if(A[i]==oo) A[i]=1;
		to[i]=pmin;
	}
	Min=oo; Max=oo; pmax=0;
	for(i=1;i<=N;i++)
		if(v[i]<Min)
		{
			Min=v[i];
			if(A[i]==Max) pmax=i;
			if(A[i]<Max)
			{
				Max=A[i];
				pmax=i;
			}
		}
}

void afisare()
{
	fout << Max << '\n';
	for(i=pmax;i;i=to[i])
		fout << i << ' ';
}

int main()
{
	citire();
	pd();
	afisare();
}