Cod sursa(job #283948)

Utilizator nparfene2004Parfene Narcis nparfene2004 Data 20 martie 2009 20:26:51
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>

using namespace std ;

int a[5001], sis[5001], next[5001], n, valmin ; 

int main()
{
	int i, j, min, max, poz, val, t, pmax ;
	
	freopen("subsir2.in","r",stdin) ;
	freopen("subsir2.out","w",stdout) ;
	
	scanf("%d", &n) ;
	for (i=1 ; i<=n ; i++)
		scanf("%d",&a[i]) ;
	
	max = 1 ; pmax = n ; valmin = a[n] ;
	sis[n] = 1 ;
	next[n] = 0 ;
	for (i=n-1 ; i>=1 ; i--)
	{
		min = 0 ;
		val = 5000001 ;
		poz = n+1 ;
		t = a[i] ;
		for (j=i+1 ; j<=n ; j++)
			if ((min<=sis[j])&&(t<=a[j])&&(a[j]<val))
			{
				min = sis[j] ;
				poz = j ;
				val = a[j] ;
			}
		if (poz <= n)
		{
			min++ ;
			sis[i] = min ;
			next[i] = poz ;
			if (max < min) { max = min ; pmax = i ; valmin = a[pmax] ;}
			else if ((max == min)&&(a[i]<valmin))
				valmin = a[i] ;
		}
		else
		{
			sis[i] = 1 ;
			next[i] = 0 ;
		}
	}
	
	//for (i=1 ; i<=n ; i++)
	//	printf("%d ",next[i]) ;
	
	printf("%d\n",max) ;
	
	while (max >= 1)
	{
		printf("%d ", pmax) ;
		max-- ; 
		min = 5000001 ;
		for (i=pmax ; i<=n ; i++) 
			if ((sis[i] == max)&&(min>a[i])&&(a[i]>=valmin))
			{
				min = a[i] ;
				pmax = i ;
			}
		valmin = min ;
	}
	printf("\n") ;
	
	return 0 ;
}