Cod sursa(job #813399)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 15 noiembrie 2012 13:33:04
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#include<cmath>
using namespace std;
int n,v[5010],sol=2000000000,ind;
int best[5010],next[5010];
bool pred[5010];

int main()
{
	int i,j,minim;
	ifstream fin("subsir2.in");
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>v[i];
	fin.close();
	
	v[0]=2000000000;
	for(i=n;i>0;i--)
	{
		best[i]=2000000000;
		minim=2000000000;
		for(j=i+1;j<=n;j++)
		{
			if(v[j]>=v[i] && v[j]<minim)
			{
				if(best[i]>best[j]+1 || (best[i]==best[j]+1 && v[j]<v[next[i]]))
				{
					best[i]=best[j]+1;
					next[i]=j;
					pred[j]=true;
				}
				minim=v[j];
			}
		}
		if(best[i]==2000000000)
			best[i]=1;
	}
	for(i=1;i<=n;i++)
	{
		if(!pred[i] && best[i]<sol)
		{
			sol=best[i];
			ind=i;
		}
	}
	
	ofstream fout("subsir2.out");
	fout<<sol<<"\n";
	while(ind)
	{
		fout<<ind<<' ';
		ind=next[ind];
	}
	fout<<"\n";
	fout.close();
	return 0;
}