Cod sursa(job #183463)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 22 aprilie 2008 10:52:43
Problema Subsir 2 Scor 83
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <stdio.h>
#define INF 10000005
int ok[5001];
int main(){
	int n,v[5001],i,j,p[5001],l[5001]={0},min=INF,poz,pozmax=0;
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	l[n]=1;
	for(i=n-1;i>=1;i--){
		min=l[i]=INF;
		for(j=i+1;j<=n;j++){
				if(v[j]>=v[i] && v[j]<min){
						min=v[j];
						if(l[j]+1<l[i]){
							l[i]=l[j]+1;
							p[i]=j;
						}
						else if(l[j]+1==l[i])
							if(v[j]<v[p[i]])
								p[i]=j;
					}
				if(v[j]>=v[i]) 
					ok[j]=1;
		}
		if(l[i]==INF) l[i]=1;
	}
	min=INF;
	for(i=1;i<=n;i++)
		if(l[i]<min && !ok[i]){
			min=l[i];
			poz=i;
		}
	printf("%d\n",min);
	while(min){
		printf("%d ",poz);
		poz=p[poz];
		min--;
	}
	return 0;
}