Cod sursa(job #319343)

Utilizator irene_mFMI Irina Iancu irene_m Data 31 mai 2009 16:03:24
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream.h>
#define MinV 1000000
int v[5005],l[5005],p[5005],n,minp;

void cit()
{
	int i;
	ifstream fin("subsir2.in");
	fin>>n; minp=1;
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
		if(v[i]<v[minp])
			minp=i;
	}
	fin.close();
}

void sol()
{
	int i,mina,minv,j,poz;
	l[n]=1; p[n]=1;
	for(i=n-1;i>=1;i--)
	{
		mina=MinV;
		minv=MinV;
		poz=0;
		for(j=i+1;j<=n;j++)
			if(v[i]<=v[j] && l[j]<mina && v[j]<minv)
			{
				mina=l[j]; minv=v[j];
				poz=j;
			}
		if(poz!=0)
		{
			l[i]=l[poz]+1;
			p[i]=poz;
		}
		else
		{
			l[i]=1;
			p[i]=i;
		}
	}
}

void afis()
{
	int poz;
	ofstream fout("subsir2.out");
	fout<<l[minp]<<'\n';
	fout<<minp<<" ";
	poz=p[minp];
	while(poz!=1)
	{
		fout<<poz<<" ";
		poz=p[poz];
	}
	fout.close();
}

int main()
{
	cit();
	sol();
	afis();
	return 0;
}