Cod sursa(job #16077)

Utilizator horaxCont de teste horax Data 12 februarie 2007 03:17:55
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>

#define max 5001

#define input "subsir2.in"
#define output "subsir2.out"

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

void Citire();
void Rezolva();
void Scrie();

int main()
{
    Citire();
    Rezolva();
    Scrie();
    
    return 0;

}

void Citire()
{
	FILE *in;

	long i;
	
	in = fopen ( input, "r");


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

	for(i=1; i<=n; i++)
		fscanf(in, "%ld", &a[i]);
    
}    
void Rezolva()
{
    long i;
    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;
            expandat[j] = 1;
            }
		if(lmax)
		{
			lung[i]=lmax+1;
			cont[i]=minim;
		}

    }    

	for(i=1; i<=n; i++)
        if(!expandat[i])
		if(lung[i]>LMAX)
		{
			LMAX=lung[i];
			pozitia=i;
		}
		else if((lung[i]==LMAX) && a[i]<a[pozitia])
			pozitia =i;

	

}
void Scrie()
{
    FILE *out;
	out = fopen (output, "w");
	fprintf(out, "%ld\n", LMAX);

    int	i=pozitia;

	k=0;

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

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

}