Cod sursa(job #415301)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 11 martie 2010 08:28:53
Problema Subsir 2 Scor 76
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<stdio.h>
#include<bitset>
using namespace std;

int a[5005],lg[5005],d[5005],i,j,n,mi=10000000,pozmin;
bitset <5005> fol;

int main()
{
	freopen("subsir2.in","r",stdin);
	freopen("subsir2.out","w",stdout);
	
	scanf("%d",&n);
	
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	
	for(i=n;i>=1;--i)
	{
		lg[i]=1;
		
		int mar=10000000;
		
		for(j=i+1;j<=n;++j)
		{
			if(a[i]<=a[j]) 
			{	
				fol[j]=1;
				if(a[j]<mar&&(lg[i]==1||lg[i]>=lg[j]+1))
				{
					mar=a[j];
					lg[i]=lg[j]+1;
					d[i]=j;
				}
			}
		}
	}
	
	for(i=1;i<=n;++i) 
		if(!fol[i]&&lg[i]<mi)
		{
			mi=lg[i];
			pozmin=i;
		}
		else if(!fol[i]&&lg[i]==mi&&a[i]<a[pozmin])
		{
			mi=lg[i];
			pozmin=i;
		}
		
	i=pozmin;
	printf("%d\n",mi);

	while(i)
	{
		printf("%d ",i);
		i=d[i];
	}
	
	printf("\n");
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}