Cod sursa(job #2134562)

Utilizator shantih1Alex S Hill shantih1 Data 18 februarie 2018 08:14:46
Problema Subsir 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");

int n,i,j,nr,mx,rz,mn,id,v[5005],pre[5005],lng[5005],da[5005],nu[5005];
bool mxm[5005];

int main()
{
    fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	
	lng[n+1]=n+1;
	lng[1]=1;
	pre[1]=0;
	for(i=2;i<=n;i++)
	{
		id=n+1;
		mx=-10000005;
		for(j=i-1;j>=1;j--)
			if(v[j]<=v[i])	
			{
				mxm[j]=1;
				if(v[j]>mx)
				{
					mx=v[j];
					if(lng[j]<lng[id])	id=j;		
				}
			}
		
		if(id!=n+1)
		{
			lng[i]=lng[id]+1;
			pre[i]=id;
		}
		else
		{
			lng[i]=1;
			pre[i]=0;
		}
	}
	rz=n;
	for(i=1;i<=n;i++)
	{
		if(mxm[i]==0&&lng[i]<rz)
			rz=lng[i];
		if(v[i]>mx)	
		{	mx=v[i];	id=i;	}
	}
	
	fout<<rz<<"\n";
	for(i=1;i<=rz;i++)
		da[i]=id;
	
	for(i=1;i<=n;i++)
		if(mxm[i]==0)
		{
			id=i;
			nr=0;
			while(id!=0)
			{
				nr++;	nu[nr]=id;
				id=pre[id];
			}
			nr=rz;
			if(nr==rz)
			{
				int ok=0;
				while(ok==0&&nr>0)
				{
					if(v[nu[nr]]<v[da[nr]])	ok=1;
					if(v[nu[nr]]>v[da[nr]])	ok=-1;
					nr--;
				}
				if(ok==1)
					for(j=1;j<=rz;j++)
						da[j]=nu[j];
			}
		}
	
	for(i=rz;i>=1;i--)
		fout<<da[i]<<" ";
}