Cod sursa(job #319344)

Utilizator irene_mFMI Irina Iancu irene_m Data 31 mai 2009 16:08:55
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 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=n+1; poz=n+1;
		minv=MinV;
		for(j=i+1;j<=n;j++)
			if(v[i]<=v[j])
			{
				if(l[j]<mina && v[j]<minv)
				{
					poz=j; mina=l[j];
					minv=v[j];
				}
				/*else
					if(l[j]==mina && v[j]<minv)
					{
						poz=j;
						minv=v[j];
					}*/
			}
		if(poz<=n)
		{
			l[i]=l[poz]+1;
			p[i]=poz;
		}
		else
		{
			l[i]=1;
			p[i]=1;
		}
	}
}
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;
}