Cod sursa(job #696691)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 28 februarie 2012 19:38:48
Problema Subsir 2 Scor 64
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>

#define maxn 5005
#define INF (1<<29)

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

int n,i,j;
int v[maxn],T[maxn],D[maxn];

void rec ( int poz ){
	if ( !poz ){
		return ;
	}
	
	rec(T[poz]);
	fprintf(g,"%d ",poz);
}

int main () {
	
	fscanf(f,"%d",&n);
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d",&v[i]);
	}
	
	for ( i = 1 ; i <= n ; ++i ){
		D[i] = INF;
		int val_max = -INF,val_min = INF;
		for ( j = i - 1 ; j >= 1 ; --j ){
			if ( v[j] > val_max && v[j] <= v[i] ){
				if ( D[i] > D[j] + 1 ){
					D[i] = D[j] + 1;
					T[i] = j;
				}
				else{
					if ( D[i] == D[j] + 1 ){
						if ( v[T[i]] > v[j] ){
							T[i] = j;
						}
					}
				}
			}
			if ( v[j] > val_max && v[j] <= v[i] )	val_max = v[j];
			if ( v[j] < val_min )	val_min = v[j];
		}
		if ( val_min > v[i] ){
			D[i] = 1;
		}
	}
	
	int sol = INF,u = 0;
	int val_max = -INF;
	for ( i = n ; i >= 1 ; --i ){
		if ( D[i] > val_max ){
			if ( D[i] < sol ){
				sol = D[i]; u = i;
			}
			else{
				if ( D[i] == sol ){
					if ( v[T[i]] < v[u] ){
						u = i;
					}
				}
			}
		}
		
		if ( v[i] > val_max ){
			val_max = v[i];
		}
	}
	
	fprintf(g,"%d\n",sol);
	rec(u);
	fprintf(g,"\n");
	
	fclose(f);
	fclose(g);
	
	return 0;
}