Pagini recente » Cod sursa (job #2540616) | Cod sursa (job #1822506) | Cod sursa (job #178256) | Cod sursa (job #1814617) | Cod sursa (job #313502)
Cod sursa(job #313502)
using namespace std;
#include<cstdio>
#define Inf 0x3f3f3f3f
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 = -Inf;
k = -1;
for(j=i-1;j>0;--j)
{
if(a[j] > a[i] || max == 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);
}