Cod sursa(job #855449)

Utilizator tibi9876Marin Tiberiu tibi9876 Data 14 ianuarie 2013 23:24:15
Problema Subsir 2 Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include<fstream>
using namespace std;

int a[5001],b[5001],c[5001],i,j,n,mx,x;

ifstream f("subsir2.in");
ofstream g("subsir2.out");

int main()
{
	f >> n;
	for (i=1;i<=n;i++)
		f >> a[i];
	b[n]=1;
	for (i=n-1;i>=1;i--)
	{
		b[i]=1;
		for (j=i+1;j<=n;j++)
			if ((a[j]>=a[i]) && ((b[j]+1>b[i]) || ((b[j]+1==b[i]) && (a[j]<a[c[i]]))))
			{
				b[i]=b[j]+1;
				c[i]=j;
			}
	}
	for (i=1;i<=n;i++)
		if (b[i]>mx)
		{
			mx=b[i];
			x=i;
		}
	g << b[x] << "\n";
	while (x!=0)
	{
		g << x << ' ';
		x=c[x];
	}
}