Pagini recente » Cod sursa (job #2469500) | Istoria paginii runda/ojiii/clasament | Istoria paginii runda/oji12345678 | Istoria paginii happy-birthday-infoarena-2014 | Cod sursa (job #341001)
Cod sursa(job #341001)
#include <stdio.h>
#define DIM 5005
int a[DIM],best[DIM],urm[DIM],ok[DIM];
int n,nrmin,ind;
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
scanf ("%d",&a[i]);
}
void print (int val)
{
printf ("%d ",val);
if (urm[val]!=val)
print (urm[val]);
}
void solve ()
{
int i,j,imin,min,nmin;
for (i=n; i>=1; --i)
{
for (ok[i]=best[i]=1,urm[i]=i, min=nmin=DIM, j=i+1; j<=n; ++j)
if (a[j]>=a[i] && a[j]<nmin)
{
ok[j]=0;
if (best[j]<min)
{
min=best[j];
imin=j;
}
else if (best[j]==min && a[j]<a[imin])
imin=j;
if (a[j]<nmin)
nmin=a[j];
}
if (min!=DIM)
{
best[i]=min+1;
urm[i]=imin;
}
}
}
void show ()
{
int i;
for (nrmin=DIM, i=1; i<=n; ++i)
if (ok[i])
if (best[i]<nrmin)
{
nrmin=best[i];
ind=i;
}
else if (best[i]==nrmin && a[i]<a[ind])
ind=i;
printf ("%d\n",best[ind]);
print (ind);
}
int main ()
{
freopen ("subsir2.in","r",stdin);
freopen ("subsir2.out","w",stdout);
read ();
solve ();
show ();
return 0;
}