Cod sursa(job #537115)

Utilizator slycerdan dragomir slycer Data 20 februarie 2011 10:00:35
Problema Subsir 2 Scor 36
Compilator c Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <stdio.h>
#include <stdlib.h>

long data[5001]; 
long lungime[5001]; 
long back[5001]; 

long * getSolutie( int i ){
	long * ret = NULL;  
	ret = malloc(lungime[i]*sizeof(long));//[ lungime[i]];
	int j;
	long aux = i; 
	for ( j=lungime[i]-1; j>=0; j--){
		ret[j] = aux+1; 
		aux = back[aux]; 
		
	}
	return ret; 
}

int main(){
	

	int n; 
	FILE * in = fopen("subsir2.in","r");
	FILE * out = fopen("subsir2.out","w");
	
	fscanf(in,"%d",&n);
	
	int i,j; 
	for ( i=0; i<n; i++){
		fscanf(in,"%ld",&data[i]);
	}
	
	for ( i=0; i<n; i++){
		lungime[i] = 1; 
		back[i] = -1; 
		for ( j=0; j<i-1; j++){
			if ( data[j]<data[i]){
				
				if ( lungime[j]+1==lungime[i]){
					if ( back[i]>=0 && data[j]<data[ back[i] ]){
						back[i] = j; 
					}
				}
				
				if ( lungime[j]+1>lungime[i]){
					lungime[i]= lungime[j]+1; 
					back[i] = j; 
				}
			}
		}
	}
	
	long lungimeMaxima = 0; 
	long * maxSol = NULL;
	for ( i=0; i<n; i++){
		if ( lungime[i] > lungimeMaxima){
			lungimeMaxima = lungime[i]; 
			maxSol = getSolutie( i ); 
		}
	}
	
	
	
	for ( i=0; i<n; i++){
		if ( lungime[i] == lungimeMaxima ){
			long * aux = getSolutie(i);
			for ( j=0; j<lungimeMaxima; j++){
				if ( data[ aux[j]]==data[maxSol[j]]){
					continue; 
				} 
				if ( data[ aux[j]]<data[maxSol[j]] ){					
					maxSol = aux; 
					break; 
				}
				if ( data[ aux[j]]>data[maxSol[j]] ){
					break; 
				}
			}
		}
	}
	
	fprintf(out,"%ld\n",lungimeMaxima);
	for ( i=0; i<lungimeMaxima; i++){
		fprintf(out,"%ld ",maxSol[i]);
	}
	
	
	fclose( out ); 
	fclose(in); 
		
	return 0; 
}