Cod sursa(job #282045)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 16 martie 2009 19:55:16
Problema Subsir 2 Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#define vmax 1000010
#define lm 5010

int v[lm], a[lm], b[lm], c[lm], r[lm], n;

int main()
{
    freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	int i, min, j, ok;
	for (i=1; i<=n; i++) scanf("%d",&v[i]);
	v[0]=-vmax;
	for (i=n; i>0; i--)
	{
		a[i]=vmax;
		min=vmax;
		ok=0;
		for (j=i+1; j<=n; j++)
		{
			if (v[j]>=v[i] && v[b[j]]<v[i])
			{
    			if (a[j]+1<a[i])
				{
					a[i]=a[j]+1;
					min=v[j];
					c[i]=j;
					b[j]=i;
					ok=1;
				} else
				if (a[j]+1==a[i] && min>v[j])
				{
					min=v[j];
					c[i]=j;
					b[j]=i;
				}
            }
        }
		if (!ok) a[i]=1;
    }
	min=vmax;
	for (i=1; i<=n; i++)
		if (!b[i] && a[i]<min) min=a[i];
    printf("%d\n",min);
	int l=1, p;
	v[0]=vmax;
	for (i=1; i<=n; i++)
		if (!b[i] && a[i]==min)
		{
            p=i;
			ok=0;
			for (j=1; j<=min; j++)
			{
				if (v[p]<v[r[j]])
				{
				    ok=1;
					break;
				} else
				if (v[p]>v[r[j]]) break;
				p=c[p];
			}
			p=i;
			if (ok)
			    for (j=1; j<=min; j++)
				{
					r[j]=p;
					p=c[p];
                }
        }
	for (i=1; i<=min; i++) printf("%d ",r[i]);
}