Cod sursa(job #113526)

Utilizator ScrazyRobert Szasz Scrazy Data 10 decembrie 2007 18:15:01
Problema Subsir 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#define NMAX 5099
#define inf 10000000

long V[NMAX];
long T[NMAX], A[NMAX], mina, minai, n;
long min;

int main()
{
    freopen("subsir2.in","r",stdin);
    freopen("subsir2.out","w",stdout);

    scanf("%d", &n);
    int i,j;

    for (i=1; i<=n; ++i)
	scanf("%ld", V+i);

    A[n]=1;T[n]=n;
    for (i=n-1; i>=1; --i)
    {
	min=inf;
	mina=inf;
	for (j=i+1; j<=n; ++j)
	    if (V[j]>=V[i] && min>V[j]) 
	    {
		min=V[j];
		if (A[j]<mina)
		{
		    mina=A[j];
		    minai=j; 
		}
		else if (mina==A[j] && V[minai]>V[j])
		    minai=j;
	    }
	if (mina==inf) 
	{
	    A[i]=1;
	    T[i]=i;
	}
	else
	{ 
	    A[i]=mina+1; 
	    T[i]=minai;
	}
    } 

    min=V[1];
    minai=1;
    for (i=2; i<=n; ++i)
	if (min>V[i]) {min=V[i];minai=i;}
   /* for (i=1; i<=n; ++i)
	if (min==V[i] && A[minai]>A[i]) minai=i;
	*/


    printf("%d\n", A[minai]);
    //printf("%ld ", minai); 
    
    i=minai;

    while (T[i]!=i)
    {
	printf("%ld ", i);
	i=T[i];
    }
    printf("%ld", i);

    fclose(stdin);
    fclose(stdout);

    return 0;
}