Pagini recente » Cod sursa (job #1851481) | Cod sursa (job #2615201) | Cod sursa (job #2205733) | Cod sursa (job #2471201) | Cod sursa (job #313483)
Cod sursa(job #313483)
using namespace std;
#include<cstdio>
int bst[5002], a[5002], pre[5002];
int N;
inline void afis(int i)
{
if( i == -1) return;
afis(pre[i]);
printf("%d ",i);
}
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int i,j,k, max, P;
scanf("%d",&N);
for(i=1;i<=N;++i)
scanf("%d",a+i);
bst[1] = 1;
pre[1] = -1;
for(i=2;i<=N;++i)
{
bst[i] = 1; pre[i] = -1;
max = -1;
k = -1;
for(j=i-1;j>0;--j)
{
if(a[j] > a[i]) continue;
if(max < a[j])
{
if(k == -1 || bst[j] + 1 < bst[k] || ( bst[j] + 1 == bst[k] && a[j] < a[k])) k = j;
}
if(a[j] > max) max = a[j];
}
if(k != -1) { bst[i] = bst[k] + 1; pre[i] = k; }
}
P = N; max = a[N];
for(i=N-1;i>0;--i)
{
if(a[i] <= max) continue;
if(bst[i] < bst[P] || (bst[i] == bst[P] && a[i] <= a[P])) P = i;
max = a[i];
}
printf("%d\n",bst[P]);
afis(P);
}