Pagini recente » Cod sursa (job #772722) | Cod sursa (job #2171437) | Cod sursa (job #3239379) | Cod sursa (job #2665616) | Cod sursa (job #340430)
Cod sursa(job #340430)
#include <stdio.h>
#define NMAX 5005
#define Inf 0x3f3f3f3f
int N,x[NMAX],din[NMAX],t[NMAX];
int Sol[NMAX],a[NMAX],b[NMAX];
int main()
{
int i,j,most;
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;++i) scanf("%d",&x[i]);
for (i=1;i<=N;++i)
{
most=-Inf;
din[i]=Inf;
for (j=i-1;j;--j)
if (x[j] < x[i] && x[j] >= most)
{
most=x[j];
if (din[j]+1 < din[i])
{
din[i]=din[j]+1;
t[i]=j;
}
else
if (din[j]+1 == din[i] && x[t[i]] > x[j]) t[i]=j;
}
if (most == -Inf) din[i]=1;
}
int lmin=Inf;
most=-Inf;
for (i=N;i;i--)
if (x[i] >= most)
{
if (lmin > din[i]) lmin=din[i];
most=x[i];
}
printf("%d\n",lmin);
for (i=1;i<=lmin;++i) Sol[i]=Inf;
most=-Inf;
for (i=N;i;i--)
if (x[i] >= most)
{
most=x[i];
if (lmin == din[i])
{
int k=lmin;
for (j=i;j>0;j=t[j]) a[k--]=x[j];
for (j=1;Sol[j] == a[j] && j<=lmin;++j);
if (j==lmin+1) continue;
if (Sol[j] > a[j])
{
k=lmin;
for (j=i;j;j=t[j]) b[k--]=j;
for (j=1;j<=lmin;++j) Sol[j]=a[j];
}
}
}
for (i=1;i<=lmin;++i) printf("%d ",b[i]);
return 0;
}