Cod sursa(job #414274)

Utilizator lalasCont de teste lalas Data 9 martie 2010 21:39:03
Problema Subsir 2 Scor 83
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>
using namespace std;
const int maxn = 5005;
const int MAXX = 10000001;

int i , j , k , mins ,mins2, v[maxn] , n , B[maxn] ,pred[maxn] , pozmin , P , ok[maxn]; 

int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	
	scanf("%d",&n);
	for( i = 1 ; i <= n ;++i ) scanf("%d",&v[i]);
	
	for( B[n] = 1 , i = n - 1; i >= 1 ; --i ) {
		mins = maxn , mins2 = MAXX , pozmin = 0;
		ok[i] = 1;
		for( j = i + 1 ; j <= n ;++j )
			if ( v[i] <= v[j] && v[j] < mins2 )
			{ 
				ok[j] = 0;
				mins2 = v[j];
				if ( B[j] <= mins) {
				mins = B[j];
				pozmin = j;
				}
			}
		if ( mins == maxn ) mins = 0 , pozmin = i;
		B[i] = mins + 1;
		pred[i] = pozmin;
	}
	
	for ( mins = MAXX , i = 1 ; i <= n ; ++i )
		if ( ok[i] == 1 )
			if ( B[i] < mins ) mins = B[i] , pozmin = i;
		
	printf("%d\n",mins);
	
	
	for ( i = pozmin; mins-- ; ) {
		printf("%d ",i);
		i = pred[i];
	}

	
return 0;
}