Cod sursa(job #138738)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 19 februarie 2008 01:44:38
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>  
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("%d",&n);
    for (i = 1; i <= n; i++) scanf("%d", v + i);
    a[n] = 1;
    t[n] = n;

	for (i = n - 1; i >= 1; i--)
	{
		min = k = 10000 ; p = 0;

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

	}

	min = 10000;
	poz = 0;
	v[0] = 10000;

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