Cod sursa(job #531178)

Utilizator razyelxrazyelx razyelx Data 9 februarie 2011 03:53:28
Problema Subsir 2 Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream.h>
#define N 5001
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
long long a[N], n, p[N], L[N], ValMin, idxMin,best,start,ok;
void scmax(){

	int i,j;
	
	best = 5001;
	start = n;
	for (i=n; i>0; i--){
		
		L[i] = 5001; // lungimea sirului maximal i 
		p[i] = i; // urmatorul element dupa i
		ValMin = 1000001;
		
		ok = 0; 
		
		for (j=i+1; j<=n; j++){
			
						
			if(a[i] <= a[j] && a[j]<ValMin){
				
					ValMin = a[j];
					
					if (L[j]+1 < L[i]){
						L[i] = L[j] + 1;
						p[i] = j;
						
						ok = 1;
					
					} else if (L[i] == L[j]+1 && a[j] < a[p[i]]){
						p[i] = j;
					
						ok = 1;
					}
							
			}
			
		}
		if (!ok) L[i] = 1;
				
		if (a[i]<a[start]){
			best = L[i];
			start = i;
		} 
	}
	
}


int main(){
	long i,j;
	
	fin>>n;
	for (i=1;i<=n; i++)
		fin>>a[i];
	
	scmax();
	
	fout<<L[start]<<"\n";
	
	for (i=start,j=1;i<=L[start];i++,j=p[j])
		fout<<j<<" ";
		
	
	return 0;
}