Pagini recente » Cod sursa (job #2104553) | Cod sursa (job #1185324) | Cod sursa (job #1554028) | Cod sursa (job #142468) | Cod sursa (job #458328)
Cod sursa(job #458328)
#include <cstdio>
#define infile "subsir2.in"
#define outfile "subsir2.out"
#define MaxN 5024
#define Inf 1000024
int a[MaxN],lg[MaxN],poz[MaxN];
int N;
void read()
{
int i;
scanf("%d",&N);
for(i=1;i<=N;i++)
scanf("%d",&a[i]);
}
void solve()
{
int i,j,min,jmin,val;
poz[N]=0; lg[N]=1;
for(i=N-1;i>=1;i--)
{
min=Inf; val=MaxN;
for(j=i+1;j<=N;j++)
{
if(a[i]<=a[j] && a[j]<=min && (lg[j]<val || (lg[j]==val && a[j]<a[jmin])))
jmin=j, val=lg[j];
if(a[j]>=a[i] && a[j]<min)
min=a[j];
}
if(val<MaxN)
lg[i]=val+1, poz[i]=jmin;
else
lg[i]=1, poz[i]=0;
}
}
void write()
{
int i,min=Inf,valmin=Inf,pos=N+10;
for(i=1;i<=N;i++)
{
if((lg[i]<valmin || (lg[i]==valmin && a[i]<a[pos])) && a[i]<min)
valmin=lg[i], pos=i;
if(a[i]<min)
min=a[i];
}
printf("%d\n",valmin);
while(lg[pos])
{
printf("%d ",pos);
pos=poz[pos];
}
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
solve();
write();
fclose(stdin);
fclose(stdout);
return 0;
}