Cod sursa(job #499421)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 9 noiembrie 2010 19:10:57
Problema Subsir 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
using namespace std;

ofstream g("subsir2.out");
ifstream f("subsir2.in");
int n,a[5001],bst[5001],t[5001],rez=1000001,poz,minim;
int ok[5001];
void citire()
{
	int i;
	f>>n;
	minim=1000001;
	for(i=0;i<n;i++)
	{
		f>>a[i];
	if(minim<=a[i])
		continue;
	ok[i]=1;
	minim=a[i];
        }
}
int main()
{
	int i,j,minim;
	citire();
	for(i=n-1;i>=0;i--)
	{
		bst[i]=minim=1000001;
		t[i]=-1;
		for(j=i+1;j<n;j++)
		{
			if(a[j]<a[i])
				continue;
			if(minim>a[j]&&(bst[i]>bst[j]+1||(bst[i]==bst[j]+1&&a[j]<a[t[i]])))
			{
				bst[i]=bst[j]+1;
				t[i]=j;
			}
			if(minim>a[j])
				minim=a[j];
		}
		if(bst[i]==1000001)
		{
			bst[i]=1;
			t[i]=i;
		}
		if(ok[i]&&(rez>bst[i]||(rez=bst[i]&&a[i]<a[poz])))
		{
			rez=bst[i];
			poz=i;
		}
	}
	g<<rez<<"\n";
	for(i=poz;i!=t[i];i=t[i])
		g<<i+1<<" ";
	g<<i+1;
	return 0;
}