Pagini recente » Cod sursa (job #973296) | Cod sursa (job #103895) | Cod sursa (job #2154560) | Cod sursa (job #1458802) | Cod sursa (job #204196)
Cod sursa(job #204196)
#include <stdio.h>
#define maxl 5010
#define val_max 2000000
int i,j,k,n,min,ok,p;
int v[maxl],c[maxl],vine[maxl];
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++) scanf("%d",&v[i]);
c[n]=1;vine[n]=-1;
for (i=n-1; i>=1; i--)
{
min=val_max;c[i]=1;vine[i]=-1;
for (j=i+1; j<=n; j++)
{
if (v[j]>=v[i] && min>v[j] &&
(c[j]+1<c[i] || c[i]==1 || (c[j]+1==c[i] && v[vine[i]]>v[j]))
)
{
c[i]=c[j]+1;
vine[i]=j;
}
if (v[j]<min && v[j]>=v[i]) min=v[j];
}
}
min=val_max;p=val_max;
for (i=1; i<=n; i++)
if (c[i]<=min && v[i]<p)
{
p=v[i];k=i;
min=c[i];
}
printf("%d\n",c[k]);
while (k>0)
{
printf("%d ",k);
k=vine[k];
}
return 0;
}