Cod sursa(job #2134329)

Utilizator shantih1Alex S Hill shantih1 Data 17 februarie 2018 20:41:53
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 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];
bool mxm[5005];

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