Cod sursa(job #531179)

Utilizator razyelxrazyelx razyelx Data 9 februarie 2011 04:02:06
Problema Subsir 2 Scor 37
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 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, 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;
				
	}
	
}


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