Cod sursa(job #184793)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 24 aprilie 2008 12:21:04
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 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;
		}
		else if(l[i]==min && !ok[i])
			if(v[i]<v[poz])
				poz=i;
	printf("%d\n",min);
	while(min){
		printf("%d ",poz);
		poz=p[poz];
		min--;
	}
	return 0;
}