Cod sursa(job #181987)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 20 aprilie 2008 09:48:27
Problema Subsir 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <stdio.h>
#define INF 10000000
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){
		poz=0;
		l[i]=INF;
		min=INF;
		for(j=i+1;j<=n;j++){
			if(v[j]<min)
				if(v[j]>=v[i] && l[j]<l[i]){
					min=v[j];
					l[i]=l[j];
					p[i]=j;
					ok[j]=1;
				}
			if(v[j]>=v[i])
				ok[j]=1;
		}
		l[i]++;
	}
	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);
		min--;
		poz=p[poz];
	}
	return 0;
}