Pagini recente » Rating Grigore George Alexandru (jucatorul) | Cod sursa (job #2014355) | Cod sursa (job #176883) | Cod sursa (job #2014352) | Cod sursa (job #3136140)
//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;
}