Cod sursa(job #203705)

Utilizator rapidu36Victor Manz rapidu36 Data 18 august 2008 20:04:09
Problema Subsir 2 Scor 54
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<stdio.h>

const int N=5001;
const int INF=1000010;

int v[N],lung[N],urm[N],n;
bool prim[N];

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

void calcul(){
	int min;
	lung[n]=1;
	for(int i=n-1;i;--i){
		lung[i]=N;
		min=INF;
		for(int j=i+1;j<=n;++j)
			if(v[i]<=v[j]){
				prim[j]=true;
				if(v[j]<=min){
					if((lung[j]==lung[i] && v[j]<v[urm[i]]) || (lung[j]<lung[i])){
						lung[i]=lung[j];
						urm[i]=j;
					}
					min=v[j];
				}
			}
		++lung[i];
	}
	int x=1;
	for(int i=2;i<=n;++i)
		if(!prim[i])
			if((lung[i]==lung[x] && v[i]<v[x]) || (lung[i]<lung[x]))
				x=i;
	printf("%d\n%d",lung[x],x);
	x=urm[x];
	while(x){
		printf(" %d",x);
		x=urm[x];
	}
	printf("\n");
}

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