Pagini recente » Cod sursa (job #2759879) | Cod sursa (job #805848) | Cod sursa (job #299347) | Cod sursa (job #1238258) | Cod sursa (job #19181)
Cod sursa(job #19181)
#include <cstdio>
#define maxn 1<<13
#define oo 0x3f3f3f3f
int n, a[maxn], bst[maxn], t[maxn], rez=oo, poz, min;
char ok[maxn];
void citire()
{
int i;
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w",stdout);
scanf("%d\n", &n);
for(i=0;i<n;i++)
{
scanf("%d ", a+i);
if(min<=a[i]) continue;
ok[i]=1;
min=a[i];
}
}
int main()
{
int i, j, min;
citire();
for(i=n-1;i>=0;i--)
{
bst[i]=min=oo;
t[i]=-1;
for(j=i+1;j<n;j++)
{
if(a[j]<a[i]) continue;
if(min>a[j]&&(bst[i]>bst[j]+1||bst[i]==bst[j]+1&&a[j]<a[t[i]]))
{
bst[i]=bst[j]+1; t[i]=j;
}
if(min>a[j]) min=a[j];
}
if(bst[i]==oo)
{
bst[i]=1;
t[i]=i;
}
if(ok[i]&&(rez>bst[i]||(rez=bst[i]&&a[i]<a[poz])))
{
rez=bst[i]; poz=i;
}
}
rez=0;
for(i=poz;i!=t[i];i=t[i]) rez++;
printf("%d\n", rez+1);
for(i=poz;i!=t[i];i=t[i]) printf("%d ", i+1);
printf("%d\n", i+1);
return 0;
}