Pagini recente » Cod sursa (job #995730) | Profil Andrei-Horia | Istoria paginii utilizator/carjamihail | Cod sursa (job #1273732) | Cod sursa (job #282045)
Cod sursa(job #282045)
#include <cstdio>
#define vmax 1000010
#define lm 5010
int v[lm], a[lm], b[lm], c[lm], r[lm], n;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
int i, min, j, ok;
for (i=1; i<=n; i++) scanf("%d",&v[i]);
v[0]=-vmax;
for (i=n; i>0; i--)
{
a[i]=vmax;
min=vmax;
ok=0;
for (j=i+1; j<=n; j++)
{
if (v[j]>=v[i] && v[b[j]]<v[i])
{
if (a[j]+1<a[i])
{
a[i]=a[j]+1;
min=v[j];
c[i]=j;
b[j]=i;
ok=1;
} else
if (a[j]+1==a[i] && min>v[j])
{
min=v[j];
c[i]=j;
b[j]=i;
}
}
}
if (!ok) a[i]=1;
}
min=vmax;
for (i=1; i<=n; i++)
if (!b[i] && a[i]<min) min=a[i];
printf("%d\n",min);
int l=1, p;
v[0]=vmax;
for (i=1; i<=n; i++)
if (!b[i] && a[i]==min)
{
p=i;
ok=0;
for (j=1; j<=min; j++)
{
if (v[p]<v[r[j]])
{
ok=1;
break;
} else
if (v[p]>v[r[j]]) break;
p=c[p];
}
p=i;
if (ok)
for (j=1; j<=min; j++)
{
r[j]=p;
p=c[p];
}
}
for (i=1; i<=min; i++) printf("%d ",r[i]);
}