Cod sursa(job #501419)

Utilizator bora_marianBora marian bora_marian Data 14 noiembrie 2010 22:47:52
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<fstream>
using namespace std;
int v[5009],n,minim;
int l[5009],poz[5009],incepe[5009],solutii[5009],nr,pozitia;
void minimul();
void solve();
int main()
{
	ifstream fin("subsir2.in");
	ofstream fout("subsir2.out");
	fin>>n;
	int i;
	for(i=1;i<=n;i++)
	   fin>>v[i],l[i]=n,poz[i]=-1;
	solve();
	minimul();
	fout<<minim<<endl;
	for(i=pozitia;i>=1;i=poz[i])
		fout<<i<<" ";
	
	return 0;
}   
void solve()
{
	int i,j;
	l[n]=1;
	for(i=n-1;i>=1;i--)
	{
		int val=+1000000;
		for(j=i+1;j<=n;j++)
			if(v[j]>=v[i])
			{	
				if(v[j]<val)
				{
				    if(l[j]+1<l[i])
				        l[i]=l[j]+1,poz[i]=j;
				    else
				       {
						   if(l[j]+1==l[i] && v[j]<=v[poz[i]])
								poz[i]=j;
						}		
				    val=v[j];
				}    
			    incepe[j]=1;
			}
		if(l[i]==n)
		   l[i]=1;	
	}
}
void minimul()
{
	int i,valstart;
	minim=n;
	for(i=1;i<=n;i++)
		if(l[i]<minim && incepe[i]!=1)
			minim=l[i],pozitia=i,valstart=v[i];
		else
		   if(l[i]==minim && incepe[i]!=1 && v[i]<valstart)
				pozitia=i,valstart=v[i];
		
}