Cod sursa(job #405218)

Utilizator xtephanFodor Stefan xtephan Data 27 februarie 2010 19:24:03
Problema Subsir 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<stdio.h>
#include<algorithm>

using namespace std;


int a[5001], c[5001], pre[5001];
int n;

void cit();
void rez();
void afis();

int main() {
	
	freopen("subsir2.in", "r", stdin);
	freopen("subsir2.out", "w", stdout);
	
	cit();
	rez();
	afis();
	
	return 0;
}


void cit() {
	scanf("%d", &n);
	
	for(int i=1;  i<=n; i++)
		scanf("%d", &a[i]);
	
}


void rez() {
	
	long i,j,min, minp;
	
	c[n]=1;
	pre[n]=-1;
	
	
	for(i=n-1; i>=1; i--) {
		
		min=2000002;
		
		for(j=i+1; j<=n; j++) {
			
			if(a[i]<a[j]) {
				if(min>a[j])
					min=a[j], minp=j;
			}
			
		}
	
		if(min!=2000002)
			c[i]=c[minp]+1, pre[i]=minp;
		else
			c[i]=1, pre[i]=-1;
		
	}
}


void afis() {
	
	int i;
	int tot=-1,k;
	
	for(i=1; i<=n; i++)
		//tot=max(tot,c[i]);
		if(tot<c[i])
			tot=c[i], k=i;
		
		printf("%d\n",tot);
		
	int inc =k;
	
	while(1) {
		printf("%d ", inc);
		inc=pre[inc];
		if(inc==-1)
			break;
	}
		

}