Cod sursa(job #269682)

Utilizator BaduBadu Badu Badu Data 3 martie 2009 11:07:25
Problema Subsir 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 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;}
	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;
}