Cod sursa(job #87182)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 26 septembrie 2007 20:07:22
Problema Subsir 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
# include <stdio.h>

const long int MAXN=5000;
long int len,n,v[MAXN+1],solv[MAXN+1],sollen,solf;
struct {long int inf,next;} set[MAXN+1];

void citire()
{
FILE *f=fopen("subsir2.in","r");
fscanf(f,"%ld",&n);
long int i;
for (i=1;i<=n;i++) fscanf(f,"%ld",&v[i]);
fclose(f);
}

void calculeaza()
{
long int i,j,minsofar;
set[n].next=0;set[n].inf=1;
for (i=n-1;i>=1;i--)
	{
	set[i].inf=-1;set[i].next=0;
	for (j=i+1,minsofar=-1;j<=n;j++)
		{
		//trebuie sa fie >=v[i] si <minsofar
		if (v[j]>=v[i]&&(minsofar==-1||v[j]<minsofar))
			{
			minsofar=v[j];
			//sa vedem daca e cumva o sol mai buna
			if (set[i].inf==-1||set[i].inf>set[j].inf+1)
				{
				set[i].inf=set[j].inf+1;
				set[i].next=j;
				}
			else if (set[i].inf==set[j].inf+1&&v[set[i].next]>v[j])
				{
				set[i].next=j;
				}
			}
		}
	if (minsofar==-1)
		{
		set[i].next=0;
		set[i].inf=1;
		}
	}
//sa vedem care e castigatorul
sollen=-1;
for (i=1,minsofar=-1;i<=n;i++)
	if (minsofar==-1||v[i]<minsofar)
		{
		minsofar=v[i];
		if (sollen==-1||sollen>set[i].inf||(sollen==set[i].inf&&v[solf]>v[i]))
			{
			sollen=set[i].inf;
			solf=i;
			}
		}
}

void scrie()
{
long int i,alr=0;
FILE *g=fopen("subsir2.out","w");
fprintf(g,"%ld\n",sollen);
for (;solf;solf=set[solf].next)
	{
	if (alr) fprintf(g," ");
	fprintf(g,"%ld",solf);
	alr++;
	}
fprintf(g,"\n");
fcloseall();
}

int main()
{
citire();
calculeaza();
scrie();
return 0;
}