Mai intai trebuie sa te autentifici.

Cod sursa(job #138701)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 19 februarie 2008 00:40:23
Problema Subsir 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>  
long int n, v[5001], a[5001], t[5001], k, ok[5001];

void afis(int i)
{
	printf("%d ",i);
	if (i != t[i]){ i = t[i]; afis(i);}
}
int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	int i, j, min, poz, p;

    scanf("%ld",&n);
    for (i = 1; i <= n; i++) scanf("%ld", v + i);
    a[n] = 1;

	for (i = n; i >= 1; i--)
	{
		min = 10000;
		k = v[i+1];
                p = i + 1;
		for (j = i + 1; j <= n; j++)
		{
			if (k > v[j]) k = v[j], p = j;
			if (v[i] < v[j] && a[j] <= min )
			{
			   if (p != j)
			   {
			      if (k > v[j])min = a[j], poz = j;
			   }
			   else min = a[j], poz = j;
			}			
			if (v[i] <= v[j]) ok[j] = 1;
		}
		if (min != 10000)
		{
			t[i] = poz;
			a[i] = min + 1;
		}
		else a[i] = 1, t[i] = i;

	}

	min = 10000;

	for (i = 1; i <= n; i++) if (a[i] < min && !ok[i]) min = i;	
	
	printf("%d\n",a[min]);
	afis(min);  
    return 0;  
}