Cod sursa(job #667541)

Utilizator suzanicaSuzanica Mihu suzanica Data 23 ianuarie 2012 12:40:32
Problema Subsir 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <cstdio>
using namespace std;
int n,sol[5005],bf[5005],v[5005],i,j,min,p,s;
int main()
{	
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
		scanf("%d",&v[i]);
	for (i=n;i>0;--i)
	{
		min=111111111;
		s=min;
		for (j=i+1;j<=n;++j)
			if ((v[j]>=v[i]) && (v[j]<min))
				{
					min=v[j];
					if (sol[j]<=s)
						s=sol[j],p=j;
			}
		if (min==111111111)
			sol[i]=1;
		else
				sol[i]=sol[p]+1,bf[i]=p;
	}
	min=sol[1],p=1,j=v[1];
	for (i=2;i<=n;++i)
		if (v[i]<j)
		{
			j=v[i];
			if (sol[i]<=min) 
				min=sol[i],p=i;
		}
	printf("%d\n%d ",min,p);
	while (--min)
	{p=bf[p];printf("%d ",p);}

return 0;
}