Cod sursa(job #181881)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 19 aprilie 2008 09:20:52
Problema Subsir 2 Scor 46
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]=0;
		min=INF;
		for(j=i+1;j<=n;j++)
			if(v[j]>v[i] && l[j]>l[i] && v[j]<min){
				min=v[j];
				l[i]=l[j];
				p[i]=j;
				ok[j]=1;
			}
			else if(v[j]>v[i])
				ok[j]=1;
		l[i]++;
	}
	min=INF;
	for(i=1;i<=n;i++)
		if(!ok[i])
			if(l[i]<min){
				min=l[i];
				pozmax=i;
			}
	printf("%d\n",min);
	while(min){
		printf("%d ",pozmax);
		min--;
		pozmax=p[pozmax];
	}
	return 0;
}