Pagini recente » Cod sursa (job #368015) | Cod sursa (job #1701720) | Cod sursa (job #2697659) | Cod sursa (job #1553861) | Cod sursa (job #340441)
Cod sursa(job #340441)
#include <stdio.h>
#define NMAX 5005
#define Inf 2000000
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;
}