Cod sursa(job #3136140)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 5 iunie 2023 15:12:08
Problema Subsir 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
//Ilie Dumitru
#include<cstdio>
const int NMAX=5005;
const int VALMAX=1<<20;

int N;
int v[NMAX];
int len[NMAX];
int next[NMAX];
bool doable[NMAX];

void gen()
{
	int i, j, min;

	for(i=N-1;i>-1;--i)
	{
		doable[i]=1;
		len[i]=NMAX;
		next[i]=N;

		min=VALMAX;
		for(j=i+1;j<N;++j)
		{
			if(v[i]<=v[j])
			{
				doable[j]=0;
				if(v[j]<min && len[j]+1<=len[i])
				{
					next[i]=j;
					len[i]=len[j]+1;
				}
				if(v[j]<min)
					min=v[j];
			}
		}
		if(len[i]==NMAX)
			len[i]=1;
	}
}

int main()
{
	FILE* f=fopen("subsir2.in", "r"), *g=fopen("subsir2.out", "w");
	int i, minLen=NMAX, minPos=NMAX;

	fscanf(f, "%d", &N);
	for(i=0;i<N;++i)
		fscanf(f, "%d", v+i);

	gen();

	for(i=N-1;i>-1;--i)
		if(doable[i] && len[i]<minLen)
			minLen=len[i], minPos=i;

	fprintf(g, "%d\n", minLen);
	for(i=minPos;i<N;i=next[i])
		fprintf(g, "%d ", i+1);

	fclose(f);
	fclose(g);
	return 0;
}