Cod sursa(job #15046)

Utilizator raula_sanChis Raoul raula_san Data 10 februarie 2007 16:24:32
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#define dim 5001
using namespace std;

long LMAX, lmax, pozitia, lung[dim], a[dim], cont[dim], i, j, v[dim], k, n, minim;

int main() {
	FILE *f, *g;

	f = fopen ("subsir2.in", "r");
	g = fopen ("subsir2.out", "w");

	fscanf(f, "%ld", &n);

	for(i=1; i<=n; i++) fscanf(f, "%ld", &a[i]);

    fclose(f);

	lung[1]=1;
	cont[1]=0;

	for(i=2; i<=n; i++)
	{
		lmax=0;
		lung[i]=1;
		cont[i]=0;

		for(j=i-1; j; j--)
			if(a[i]>=a[j])
			if( lmax<lung[j])
			{
				lmax=lung[j];
				minim=j;
			}
			else
				if((lmax==lung[j])&&(a[minim]>a[j]))
					minim=j;

		if(lmax)
		{
			lung[i]=lmax+1;
			cont[i]=minim;
		}

		if(lung[i]>LMAX)
		{
			LMAX=lung[i];
			pozitia=i;
		}
		else if((lung[i]==LMAX) && a[i]<a[pozitia])
			pozitia =i;

	}

	fprintf(g, "%ld\n", LMAX);

	i=pozitia;

	k=0;

	while(i)
	{
		v[++k]=i;
		i=cont[i];
	}

	for(i=k; i; i--)
		fprintf(g, "%ld ", v[i]);

    fclose(g);

	return 0;
}