Pagini recente » Cod sursa (job #897427) | Cod sursa (job #115787) | Cod sursa (job #2275863) | Cod sursa (job #2706872) | Cod sursa (job #17439)
Cod sursa(job #17439)
#include<stdio.h>
const int maxn = 10001;
const int inf = 100000000;
int a[maxn];
int i;
int n;
int min;
int la[maxn];
int le[maxn];
int poz;
int j;
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]+=1000001;
}
for(j=n;j>=1;j--)
{
le[j]=inf;
la[j]=0;
min=inf;
for(i=j+1;i<=n;i++)
{
if (a[i]<min&&a[i]>=a[j]) min=a[i];
if (min==a[i]&&a[i]>=a[j]&&(le[i]+1<le[j]||(le[i]+1==le[j]&&a[la[j]]>a[i])))
{
le[j]=le[i]+1;
la[j]=i;
}
}
if (le[j]==inf) le[j]=1;
}
min=inf;
int min1=inf;
poz=inf;
for(i=1;i<=n;i++)
{
if (a[i]<min1) min1=a[i];
if (a[i]==min1&&(le[i]<min||(a[poz]>a[i]&&le[i]==min)))
{
min=le[i];
poz=i;
}
}
printf("%d\n",le[poz]);
while(poz)
{
printf("%d ",poz);
poz=la[poz];
}
return 0;
}