Cod sursa(job #414205)

Utilizator lalasCont de teste lalas Data 9 martie 2010 20:28:17
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 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] ,nxt[maxn] , pozmin , P; 

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 ; i >= 1 ; --i ) {
		mins = maxn , mins2 = MAXX;
		for( j = i + 1 ; j <= n ;++j )
			if ( v[i] <= v[j] && v[j] < mins2  && B[j] < mins) { 
				mins = B[j];
				mins2 = v[j];
			}
		if ( mins == maxn ) mins = 0;
		B[i] = mins + 1;
	}
	
	for(mins = v[1], P = 1, i = 2 ; i <= n ;++i ) {
		if  ( v[i] < mins ) {
			if ( B[i] < B[P] || ( B[P] == B[i] && v[P] > v[i]))
				P = i;
		}
	}
	
	printf("%d\n%d ",B[P] ,P);
	for( mins = B[P] - 1;  mins; ){
		mins2 = MAXX;
		for( j = P + 1 ; j <= n ; ++j  ){
			if ( v[j] < mins2 ) mins2 = v[j];
			if (B[j] == mins && v[j] >= v[P] && v[j] <= mins2) pozmin = j;
		}
		printf("%d ",pozmin); P = pozmin;
		mins --;
	}

	
return 0;
}