Cod sursa(job #2134814)

Utilizator shantih1Alex S Hill shantih1 Data 18 februarie 2018 12:44:16
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 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,ok,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];
	rz=n;
	for(i=n;i>=1;i--)
	{
		mn=10000005;
		mx=n+1;
		for(j=i+1;j<=n;j++)
			if(v[j]>=v[i]&&v[j]<mn)
			{
				mn=v[j];
				mxm[j]=1;
				if(lng[i]>=lng[j]+1||lng[i]==0)
				{
					lng[i]=lng[j]+1;
					pre[i]=j;
				}
			}
		if(pre[i]==0)
		{	lng[i]=1;	pre[i]=n+1;	}
	}
	mn=100000005;
	rz=n+1;
	for(i=1;i<=n;i++)
		if(mxm[i]==0)
		{
			nr=0;	id=i;
			while(id<=n)
			{
				nr++;	nu[nr]=id;
				id=pre[id];
			}
			if(nr<rz)
			{
				rz=nr;
				mn=v[i];
				for(j=1;j<=rz;j++)
					da[j]=nu[j];
			}
			if(nr==rz&&v[i]<mn)
			{
				mn=v[i];
				for(j=1;j<=rz;j++)
					da[j]=nu[j];
			}
		}
	fout<<rz<<"\n";
	for(i=1;i<=rz;i++)
		fout<<da[i]<<" ";	fout<<"\n";
}