Cod sursa(job #269694)

Utilizator BaduBadu Badu Badu Data 3 martie 2009 11:30:18
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>

int V[5001],L[5001],P[5001],n;

int main(){

	freopen("subsir2.in","rt",stdin);
	freopen("subsir2.out","wt",stdout);

	scanf("%d",&n);int i,j,min;

	for(i=1;i<=n;i++) scanf("%d",V+i);

	L[n]=1;P[n]=n;

	for(i=n-1;i>=1;i--){ min = 1000000;

		for(j=i+1;j<=n;j++){

			if(V[j]>=V[i] && V[j]<min){

				min  = V[j];

				if(L[j]+1 >= L[i]) {

					if(!P[i]){

					L[i] = L[j]+1;
					P[i]=j;  }

					else {

						if(V[P[i]] >= V[j]){

							L[i]=L[j]+1;
							P[i]=j;
						}
					}

				}
			}

			if(!L[i]) { L[i]=1; P[i]=i; }
		}
	}
	min=1000000;int poz;
	for(i=1;i<=n;i++){
		if(min>V[i]){min=V[i];poz=i;}
		if(min==V[i]) if(L[poz]<L[i]) {min=V[i];poz=i;}
        }
	min=poz;
	printf("%d\n",L[min]);
       // if(P[min]==min) printf("%d ",V[min]);
	while(P[min]!=min){

		printf("%d ",min);
		min=P[min];
	}
	printf("%d ",min);
	return 0;
}