Cod sursa(job #473301)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 28 iulie 2010 17:43:27
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>

#define file_in "subsir2.in"
#define file_out "subsir2.out"

#define nmax 6050

int n;
int a[nmax];
int v[nmax];
int t[nmax];

void citire(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (int i=1;i<=n;++i)
		 scanf("%d", &v[i]);
}

void solve(){
	
	int i,j,poz,p,rez,min;
	//A[i] = lungimea celui mai scurt subsir crescator maximal care incepe cu pozitia i 
    //T[i] = urmatorul element dupa pozitia i in cel mai scurt subsir crescator maximal 
	//       care incepe cu i (pentru reconstiutire) 
    
	a[n]=1;
	t[n]=n;
	for (i=n-1;i>=1;--i)
	{
		a[i]=0x3f3f3f3f;
		poz=0x3f3f3f3f;
		for (j=i+1;j<=n;++j)
		{
			if (v[i]<=v[j] && a[i]>=a[j]+1 && poz>v[j])
			   a[i]=a[j]+1,
			   t[i]=j;
			if (poz>=v[j] && v[j]>=v[i])
				poz=v[j];
		}
		
		if (a[i]==0x3f3f3f3f)
			 a[i]=1,
			 t[i]=i;
	}
	
	p=0;
	min=0x3f3f3f3f;
	rez=0x3f3f3f3f;
	v[p]=0x3f3f3f3f;
	
	for (i=1;i<=n;++i)
	{
		if ((a[i]<rez || (a[i]==rez && v[i]<v[p])) && v[i]<min)
            rez=a[i],
            p=i;
        if (v[i]<min)
			min=v[i];
	}
	
	printf("%d\n", rez);
	
	while(t[p]!=p)
	{
		printf("%d ", p);
		p=t[p];
	}
	printf("%d", p);
}

int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	

	return 0;
	
}