Cod sursa(job #696780)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 28 februarie 2012 20:04:39
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 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],m[maxn];

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